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);
    		} else {
    	return uniqsPositions.isEmpty()?-1:uniqsPositions.get(0);

  • 0

    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...


    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# ( and the comments to this suggests that the reindexing cost is similar in Java, even though the actual deletion is only O(1):

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

  • 0

    This wouldnt work when the char appears 3 times.

  • 0

    .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.