Java Hashing Solution


  • 10

    We simply maintain a map of all subsequence frequencies and get the subsequence with frequency 1 that has longest length.

    NOTE: This solution does not take advantage of the fact that the optimal length subsequence (if it exists) is always going to be the length of some string in the array. Thus, the time complexity of this solution is non-optimal. See https://discuss.leetcode.com/topic/85044/python-simple-explanation for optimal solution.

    public int findLUSlength(String[] strs) {
        Map<String, Integer> subseqFreq = new HashMap<>();
        for (String s : strs) 
            for (String subSeq : getSubseqs(s))
                subseqFreq.put(subSeq, subseqFreq.getOrDefault(subSeq, 0) + 1);
        int longest = -1;
        for (Map.Entry<String, Integer> entry : subseqFreq.entrySet()) 
            if (entry.getValue() == 1) longest = Math.max(longest, entry.getKey().length());
        return longest;
    }
    
    public static Set<String> getSubseqs(String s) {
        Set<String> res = new HashSet<>();
        if (s.length() == 0) {
             res.add("");
             return res;
        }
        Set<String> subRes = getSubseqs(s.substring(1));
        res.addAll(subRes);
        for (String seq : subRes) res.add(s.charAt(0) + seq);
        return res;
    }
    

  • 1
    Z

    My idea is the same, but I used bitmasks for listing subsequences in my solution


  • 0

    Firstly, find all string's subsequence, use map<subsequence, counts>, when counts== 1, find the longest length of string

    public class Solution {
        public int findLUSlength(String[] strs) {
            Map<String, Integer> map = new HashMap<>();
            for(String s : strs) add(s, map);
            int max = -1;
            for(String s : map.keySet()) {
               //only counts == 1, means not repeat
                if(map.get(s) == 1) max = Math.max(max, s.length());
            }
            return max;
        }
        void add(String s, Map<String, Integer> map) {
            int largest = (int)Math.pow(2, s.length());
             //2^n-1 sequence
            for(int i = 1; i < largest; i++) {
                StringBuilder sb = new StringBuilder();
                int j = i, k = s.length() - 1;
                while(j > 0) {
                    if((j & 1) == 1) sb.append(s.charAt(k));
                    j = (j >>> 1);
                    k--;
                }
                //subsequence
                String temp = sb.reverse().toString();
                //if exists, count ++
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
        }
    }
    

  • 0

    Another Approach.

    public int findLUSlength(String[] strs) {
           Map<String, Boolean> map = new HashMap<>();
            for (String str : strs) {
                if (map.containsKey (str)) map.put (str, false);
                else map.put (str, true);
            }
            
            for (Iterator<Map.Entry<String, Boolean>> entryIterator = map.entrySet().iterator(); entryIterator.hasNext();) {
                Map.Entry<String, Boolean> entry = entryIterator.next();
                
                if (entry.getValue()) {
                    for (Map.Entry<String, Boolean> innerEntry : map.entrySet()) {
                        if (!innerEntry.getValue() && isSubSequence (innerEntry.getKey(), entry.getKey())) {
                        	entry.setValue(false);
                        	break;
                        }
                    }
                }
            }
            
            int max = -1;
            for (Map.Entry<String, Boolean> entry : map.entrySet()) 
                if (entry.getValue()) max = Math.max (max, entry.getKey().length());
            return max;
        }
        
        private boolean isSubSequence (String s, String t) {
            int tidx = 0;
            for (int sidx = 0; sidx < s.length() && tidx < t.length(); sidx ++)
                if (s.charAt(sidx) == t.charAt(tidx)) tidx ++;
            return tidx >= t.length();
        }
    

  • 0
    P

    The time complexity is O(n 2^k), where k is the length of string. Am I wrong?


  • 0

    Share my java solution with clear comments.
    First sort by length (longest to shortest) and ignore all the duplicated string, check every potential string and return the str that is not a subsequnce of the longer ones

        public int findLUSlength(String[] strs) {
            Map<Integer, Set<String>> map = new HashMap<>();//length -> Set<String>
            Set<String> duplicate = new HashSet<>();//record all duplicated String, they will not in the result
            int maxLen = 0;//the max length of string
    
            for (String str : strs) {
                int size = str.length();
                maxLen = Math.max(maxLen, size);
    
                Set<String> set = map.get(size);
                if (set == null) {
                    set = new HashSet<>();
                    map.put(size, set);
                }
                if (!set.add(str)) {
                    duplicate.add(str);
                }
            }
    
            List<String> longer = new ArrayList<>();//record all the strings that is previously visited in the following loop(longer or equal to the lenght of the cur string)
            for (int i = maxLen; i >= 0; i--) {
                if (map.get(i) == null) {//ignore unused length
                    continue;
                }
    
                Set<String> set = map.get(i);
    
                for (String str : set) {
                    if (!duplicate.contains(str)) {//duplicated String will not in the final result
                        boolean flag = true;//potential string, flag it as true
    
                        for (String longerStr : longer) {
                            //check if the potential string is one of its previously visited strs' subsequence
                            if(isSubsequence(longerStr, str)) {
                                flag = false;
                                break;
                            }
                        }
    
                        if (flag) {
                            return i;
                        }
                    }
                    longer.add(str);//if not return, add the cur string into longer list
                }
            }
    
            return -1;
        }
    
        //if yes, then b is subsequence of a
        private boolean isSubsequence(String a, String b) {//assuming length of a >= length of b
            if (a.length() == b.length()) {//this corner check is unnecessary actually
                return a.equals(b);
            }
    
            int i = 0;
            int j = 0;
            while (i < a.length() && j < b.length()) {
                if (a.charAt(i) == b.charAt(j)) {
                    i++;
                    j++;
                } else {
                    i++;
                }
            }
            if (j == b.length()) {
                return true;
            }
            return false;
        }
    }
    

  • 0

    @Hellokitty_2015 I have the same idea as yours! And here is my version:

    class Solution {
        public int findLUSlength(String[] strs) {
            if (strs == null || strs.length < 1) {
                return -1;
            }
            if (strs.length == 1) {
                return strs[0].length();
            }
            Arrays.sort(strs, (a, b) -> (b.length() - a.length()));
            Map<String, Integer> map = new HashMap<>();
            Set<String> failStrings = new HashSet<>();
            for (String str : strs) {
                map.put(str, map.getOrDefault(str, 0) + 1);
            }
            for (String str : strs) {
                if (map.get(str) == 1 && !failStrings.contains(str)) {
                    boolean goodToGo = true;
                    for (String failString : failStrings) {
                        if (failString.length() != str.length() && isSub(failString, str)) {
                            goodToGo = false;
                            break;
                        }
                    }
                    if (goodToGo) {
                        return str.length();
                    }
                } else {
                    failStrings.add(str);
                }
            }
            return -1;
        }
        
        private boolean isSub(String main, String cand) {
            int index = 0;
            for (int i = 0; i < main.length(); ++i) {
                if (main.charAt(i) == cand.charAt(index)) {
                    ++index;
                }
                if (index == cand.length()) {
                    return true;
                }
            }
            return index == cand.length();
        }
    }
    

Log in to reply
 

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