Simple Solution, Single Pass


  • 2
    public int firstUniqChar(String s) {
    	if(s==null || s.length()==0) {
    		return -1;
    	}
    	char[] chars = s.toCharArray();
    	Map<Character,Integer> charsPositions = new HashMap<>();
    	List<Integer> uniqsPositions = new ArrayList<>();
    	for(int i=0; i<chars.length; i++) {
    		char c = chars[i];
    		if(charsPositions.containsKey(c)) {
    			Integer charFirstPosition = charsPositions.get(c);
    			uniqsPositions.remove(charFirstPosition);
    		} else {
    			charsPositions.put(c,i);
    			uniqsPositions.add(i);
    		}
    	}
    	return uniqsPositions.isEmpty()?-1:uniqsPositions.get(0);
    }
    

  • 0
    L

    Edited to add: I just realized that the re-indexing (if it occurs) has an upper bound in your function of the nth triangular number of 25 (assuming no caps, numbers, or special characters), so it's not a big deal. That makes more sense...

    Original:

    Please correct me if I'm wrong, as I haven't used Java in a while, but isn't List.remove O(n) runtime where n = index of end of list - place of item to be removed? (I think it re-indexes the entries after the one removed, so if you had a string like "abcdefabcde" you would have something like 5+4+3+2+1 re-indexing for runtime...)

    I know it's like that in C# (https://msdn.microsoft.com/en-us/library/5cw9x18z(v=vs.110).aspx) and the comments to this suggests that the reindexing cost is similar in Java, even though the actual deletion is only O(1): http://stackoverflow.com/questions/24462513/time-complexity-for-java-arraylist-removeelement

    However, I haven’t used Java for a while, so please correct me if I am mistaken or have otherwise overlooked something.


  • 0
    C

    This wouldnt work when the char appears 3 times.


  • 0
    F

    .toCharArray() scans over the string to make a copy of each element (o(n) where n is the length of the string) which would disqualify this solution as a single pass as well


Log in to reply
 

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