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

  • 0

    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.

    	 *, 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;
    				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.