Yet Another HashMap Java Solution O(n), Map Char to Index


  • 0
    X

    Use Map to map index. If index already exists, invalidate it - make the index to s.length(), for example, or Integer.MAX_VALUE if you like.

    	/**
    	 * https://discuss.leetcode.com/topic/55148/frequeny
    	 * https://discuss.leetcode.com/topic/55827/lastIndexOf(), O(n)
    	 * 		s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i)) 
    	 * </pre>
    	 */
    	public int firstUniqChar(String s) {
    		Map<Character, Integer> charIndex = new HashMap<>();
    		// 1st pass: map and check duplicate
    		for (int i = 0; i < s.length(); i++)
    			if (charIndex.containsKey(s.charAt(i))) // visited; invalidate it
    				charIndex.put(s.charAt(i), s.length()); // invalidate;
    			else
    				charIndex.put(s.charAt(i), i);
    
    		// 2nd pass: get index
    		int result = s.length(); // invalid
    		for (int index : charIndex.values())
    			result = Math.min(result, index); // 'first'=>'min index'=>'min'
    		return result == s.length() ? -1 : result;
    	}
    

    MapChar can be just a HashMap or self-defined (because char only have 256 value, you can use int[] to speed the leetcode oj. The test case here is insufficient as it looks only has char 'a'-'z'


Log in to reply
 

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