Longest Uncommon Subsequence II

LeetCode Q 522 - Longest Uncommon Subsequence II

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.

Solution

Algorithm: Sort

• First step: sort the given array. We sort the given array according to its length and also its lexicographical order.
  tips 1: It’s straightforward that we should sort the array according to length of string, since we want to find the string having the longest length and at the same time it is not the subsequence of others.
  tips 2: We also consider the lexicographical order of strings, because we want to skip duplicates.
• Second step: go through the array having the longest length and at the same time it is not the subsequence of others.
  tips: In this step, we can just check if the candidate string is the subsequence of the first string in the array. We can do this recursively or iteratively.

Code

Code:

public int findLUSlength(String[] strs) {
	// Step 1: sort the accroding to its length and lexicographical order.
	// Put the longer one first, and put the duplicates together. 
	Arrays.sort(strs, new Comparator<String>() {
        public int compare(String s1, String s2) {
            if (s1.length() != s2.length())
                return s2.length() - s1.length();
            return s1.compareTo(s2);
        }
    });

    // Step 2: traverse the array, find it
    String s = strs[0];
    int index = 1, count = 0;
    while (index < strs.length) {
    	while (index < strs.length() && s.equals(strs[index])) {
    		index++; count++;
    	}
    	if (count == 0 && (s.equals(strs[0]) || isSubsequence(strs[0], s)))
    		return s.length();
    	if (index < strs.length){
    		s = strs[index++]; count = 0;
    	}
    }
    // identify if the last string is the answer
    if (count == 0 && !isSubsequence(strs[0], s)) 
        return s.length();
    return -1;
}

// how to decide if a string is a substring of strs[0]
// Recursive method
private boolean isSubsequnce(String s1, String s2) {
	if (s2.length() == 0) return true;
	if (s1.length() == 0) return false;
	int index = s1.indexOf(s2.charAt(0));
	if (index == -1) return false;
	return isSubsequnce(s1.substring(index + 1), s2.substring(1));
}

// Iterative method
private boolean isSubsequnce(String s1, String s2) {
	int index =  -1, j = 0;
   	while (j < s2.length()) {
   	//s.indexOf(str, startIndex)
		index = s1.indexOf(s2.charAt(j++), index + 1);
		if (index == -1)
			return false;
    }
	return j == s2.length();
}