One pass O(n) space and time complexity in Java


  • 0
    L

    You could use two maps and do a single pass of the string. Using a linkedhashmap will eliminate the need of finding the need for another search:

        public int firstUniqChar(String s) {
            if(s==null || s.length()==0) {
                return -1;
            }
            Map<Character,Integer> singlemap = new LinkedHashMap<>();
            Map<Character,Integer> dups = new HashMap<>();
            for(int i=0;i<s.length();i++) {
                if(dups.containsKey(s.charAt(i))) {
                    continue;
                }
                if(singlemap.containsKey(s.charAt(i))) {
                    dups.put(s.charAt(i),singlemap.remove(s.charAt(i)));
                }
                else {
                    singlemap.put(s.charAt(i),i);
                }
                
            }
            
             return singlemap.isEmpty()?-1:singlemap.values().iterator().next();
        }
    
    

Log in to reply
 

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