522. Longest Uncommon Subsequence II

Problem

Given an array of strings strs, return **the length of the *longest uncommon subsequence* between them**. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.

• For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

  Example 1:

Input: strs = ["aba","cdc","eae"]
Output: 3

Example 2:

Input: strs = ["aaa","aaa","aa"]
Output: -1

  Constraints:

• 2 <= strs.length <= 50

• 1 <= strs[i].length <= 10

• strs[i] consists of lowercase English letters.

Solution (Java)

class Solution {
    public int findLUSlength(String[] strs) {
        int maxUncommonLen = -1;
        for (int indx1 = 0; indx1 < strs.length; indx1++) {
            boolean isCommon = false;
            for (int indx2 = 0; indx2 < strs.length; indx2++) {
                if (indx2 != indx1 && isSubSequence(strs[indx1], strs[indx2])) {
                    isCommon = true;
                    break;
                }
            }
            if (!isCommon) {
                maxUncommonLen = Math.max(maxUncommonLen, strs[indx1].length());
            }
        }
        return maxUncommonLen;
    }

    private boolean isSubSequence(String str1, String str2) {
        int indx1 = 0;
        for (int indx2 = 0; indx2 < str2.length(); indx2++) {
            if (str1.charAt(indx1) == str2.charAt(indx2)) {
                indx1++;
            }
            if (indx1 == str1.length()) {
                return true;
            }
        }
        return indx1 == str1.length();
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).