Clean Java Solution Bitmask


  • 0
    Z

    Hi There! My idea is strightforward. The idea is to find longest length among all uncommon subsequences in the given group. Thus, problem reduces to find all the uncommon subsequences. To do so, I have used bitmasks, because the string length limitation (|str| <= 10) just appeals to use it:=)

    public class Solution {
        Map<String, Integer> freqMap;
        public int findLUSlength(String[] strs) {
            if(strs.length == 0) return -1;
            freqMap = new HashMap<>();
            collectStats(strs);
            int res = 0;
            for(String str:freqMap.keySet()){
                int freq = freqMap.get(str);
                if(freq == 1){
                    res = Math.max(res, str.length());
                }
            }
            if(res == 0) return -1;
            return res;
        }
        
        private void collectStats(String [] strs){
            for(String str:strs){
                Set<String> subs = getSubs(str);
                for(String sub:subs){
                    freqMap.put(sub, freqMap.getOrDefault(sub, 0)+1);
                }
            }
        }
        
        private Set<String> getSubs(String str){
            Set<String> res= new HashSet<>();
            int n= str.length();
            int max = (1<<n)-1;
            StringBuilder build = new StringBuilder();
            for(int i = 1;i<=max;i++){
                for(int j= 0, p = 1;j<n;j++,p = p<<1){
                    if((p&i) != 0){
                        build.append(str.charAt(j));            
                    }
                }
                res.add(build.toString());
                build.setLength(0);
            }
            return res;
        }
        
        
    }

Log in to reply
 

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