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?


Log in to reply
 

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