Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/522.html

522. Longest Uncommon Subsequence II

Level

Medium

Description

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.

Example 1:

Input: “aba”, “cdc”, “eae”

Output: 3

Note:

  1. All the given strings’ lengths will not exceed 10.
  2. The length of the given list will be in the range of [2, 50].

Solution

First sort the array of strings according to the lengths in descending order. Then obtain each string’s number of occurrences of each string in the array, and use a map to store each string’s number of occurrences. Loop over the array from left to right where the longest string is visited first. If a string occurs more than once, then it must be another string’s subsequence (another string has the same content as the current string). If a string occurs only once, then it may be an uncommon subsequence. If the current string is not a subsequence of any string that has already been visited, then the current string is the longest uncommon subsequence, so return its length. If no uncommon subsequence is found, return -1.

  • class Solution {
    public int findLUSlength(String[] strs) {
        Arrays.sort(strs, new Comparator<String>() {
            public int compare(String str1, String str2) {
                if (str1.length() != str2.length())
                    return str2.length() - str1.length();
                else
                    return str1.compareTo(str2);
            }
        });
        Map<String, Integer> map = new HashMap<String, Integer>();
        int length = strs.length;
        for (int i = 0; i < length; i++) {
            String str = strs[i];
            int count = map.getOrDefault(str, 0);
            count++;
            map.put(str, count);
        }
        Set<String> set = new HashSet<String>();
        for (int i = 0; i < length; i++) {
            String str = strs[i];
            boolean isLUS = true;
            if (map.get(str) == 1) {
                for (String prevStr : set) {
                    if (isSubsequence(str, prevStr)) {
                        isLUS = false;
                        break;
                    }
                }
                if (isLUS)
                    return str.length();
            }
            set.add(str);
        }
        return -1;
    }

    public boolean isSubsequence(String str1, String str2) {
        int length1 = str1.length(), length2 = str2.length();
        int index1 = 0;
        for (int index2 = 0; index1 < length1 && index2 < length2; index2++) {
            if (str1.charAt(index1) == str2.charAt(index2))
                index1++;
        }
        return index1 == length1;
    }
}

  • class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def check(a, b):
            i = j = 0
            while i < len(a) and j < len(b):
                if a[i] == b[j]:
                    j += 1
                i += 1
            return j == len(b)

        n = len(strs)
        ans = -1

        for i in range(n):
            j = 0
            while j < n:
                if i == j or not check(strs[j], strs[i]):
                    j += 1
                else:
                    break
            if j == n:
                ans = max(ans, len(strs[i]))
        return ans

############

class Solution(object):
  def findLUSlength(self, strs):
    """
    :type strs: List[str]
    :rtype: int
    """

    def findLUSlength(a, b):
      return max(len(a), len(b)) if a != b else -1

    def isSubsequence(s, t):
      d = collections.defaultdict(list)
      for i, c in enumerate(t):
        d[c].append(i)
      start = 0
      for c in s:
        idx = bisect.bisect_left(d[c], start)
        if len(d[c]) == 0 or idx >= len(d[c]):
          return False
        start = d[c][idx] + 1
      return True

    ans = -1
    strs.sort(key=len, reverse=True)
    for i in range(len(strs)):
      flag = True
      for j in range(len(strs)):
        if i != j and (findLUSlength(strs[i], strs[j]) == -1 or isSubsequence(strs[i], strs[j])):
          flag = False
          break
      if flag:
        return len(strs[i])
    return -1


  • class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int ans = -1;
        for (int i = 0, j = 0, n = strs.size(); i < n; ++i) {
            for (j = 0; j < n; ++j) {
                if (i == j) continue;
                if (check(strs[j], strs[i])) break;
            }
            if (j == n) ans = max(ans, (int) strs[i].size());
        }
        return ans;
    }

    bool check(string a, string b) {
        int j = 0;
        for (int i = 0; i < a.size() && j < b.size(); ++i)
            if (a[i] == b[j]) ++j;
        return j == b.size();
    }
};

  • func findLUSlength(strs []string) int {
	check := func(a, b string) bool {
		j := 0
		for i := 0; i < len(a) && j < len(b); i++ {
			if a[i] == b[j] {
				j++
			}
		}
		return j == len(b)
	}

	ans := -1
	for i, j, n := 0, 0, len(strs); i < n; i++ {
		for j = 0; j < n; j++ {
			if i == j {
				continue
			}
			if check(strs[j], strs[i]) {
				break
			}
		}
		if j == n && ans < len(strs[i]) {
			ans = len(strs[i])
		}
	}
	return ans
}

All Problems

All Solutions