Took the idea from other solutions (Java) (Added a logical reasoning on why the LUS must be some String)


  • 0
    V

    LUS must be a string of the given list of strings, cannot be a part string : Let us say, for the sake of contradiction LUS is a part String sPrime, this means sPrime is not a subsequence of any other given strings. Then any add any characters to sPrime, the resultant string cannot be subsequence of any other string, therefore, we can add as many as characters but limited to the length of the string that contains sPrime (that can be the maximum).

    public class Solution {
        public int findLUSlength(String[] strs) {
            Arrays.sort(strs, new Comparator < String > () {
                public int compare(String s1, String s2) {
                    return s2.length() - s1.length();
                }
            });
            
            int maxLen = -1;
            for (int i = 0; i < strs.length; i++) {
                String curr = strs[i];
                
                boolean lus = true;
                for (int j = 0; j < strs.length; j++) {
                    if (i == j) continue;
                    if (curr.length() > strs[i].length() || isSebseq(curr, strs[j])) {
                        lus = false;
                        break;
                    }
                }
                
                if (lus) {
                    maxLen = curr.length();
                    break;
                }
            }
            
            return maxLen;
        }
        
        private boolean isSebseq(String x, String y) {
            int j = 0;
            for(int i = 0; j < x.length() && i < y.length(); i++) {
                if (x.charAt(j) == y.charAt(i)) j++;
            }
            
            return j == x.length();
        }
    }
    

Log in to reply
 

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