Java solution using two buckets: candidates & exclusions


  • 0
    A
    public class Solution {
        public int findLUSlength(String[] strs) {
            // algorithm 2017/05/17: the key to understand the problem is that any string's substring can never be the answer (if a substring is the 'longest' uncommon subsequence, or the whole string must be and even longer), hence the answer must come from one of the string as a whole
            // special case: if there is a single string which is longer than other strings, then this string itself is the 'longest' uncommon subsequence
            // solution is to put all strings into two buckets
            // exclusion bucket: these strings are duplicated and cannot be used for the 'uncommon subsequence';
            // candidate bucket: each string appears only once and the longest could be the candidate
            if (null == strs || 0 == strs.length) {
                return -1;
            }
            List<String> exclusions = new ArrayList<>();
            List<String> candidates = new ArrayList<>();
    
            for (String str : strs) {
                // already in exclusion bucket?
                if (exclusions.contains(str)) {
                    continue;
                }
                if (candidates.contains(str)) {
                    candidates.remove(str);
                    exclusions.add(str);
                    continue;
                }
    
                // not in exclusions, and not in canddiates, so we get a new candidate
                candidates.add(str);
            }
    
            // no candidate?
            if (candidates.isEmpty()) {
                return -1;
            }
            // sort candidates by length
            Collections.sort(candidates, new Comparator<String>() {
                public int compare(String str1, String str2) {
                    return str2.length() - str1.length();
                }
            });
    
            // no exclusions? we get the longest candidate as the result
            if (exclusions.isEmpty()) {
                return candidates.get(0).length();
            }
            // sort exclusions by length
            Collections.sort(exclusions, new Comparator<String>() {
                public int compare(String str1, String str2) {
                    return str2.length() - str1.length();
                }
            });
    
            for (String candidate : candidates) {
                boolean validCandidate = true;
                int LUSLengthForCandidate = -1;
                // check against all exclusions
                for (String exclusion : exclusions) {
                    LUSLengthForCandidate = findLUSlength(candidate, exclusion);
                    if (-1 == LUSLengthForCandidate) {
                        validCandidate = false;
                        break;
                    }
                }
                if (validCandidate) {
                    assert -1 != LUSLengthForCandidate;
                    return LUSLengthForCandidate;   // return here because we check longest string first
                }
            }
    
            return -1;
        }
    
        private int findLUSlength(String candidate, String exclusion) {
            assert null != exclusion && null != candidate;
            int exclusionLen = exclusion.length();
            int candidateLen = candidate.length();
    
            // candidate is longer, we immeidately return
            if (exclusionLen < candidateLen) {
                return candidateLen;
            }
    
            // candidate is shorter, let us see whether we can build an uncommon subsequence
            int exclusionIndex = -1;
            for (int candidateIndex = 0; candidateIndex < candidateLen; candidateIndex++) {
                char ch = candidate.charAt(candidateIndex);
                exclusionIndex = exclusion.indexOf(ch, exclusionIndex + 1);
                if (-1 == exclusionIndex) {
                    return candidateLen;    // cannot find the next char inside exclusion
                }
            }
    
            return -1;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.