Short O(n) Java solution


  • 0
    S
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> chToIdx = new HashMap<>();
        int maxLength = 0, minIdx = 0;
        for (int i = 0; i < s.length(); i++) {
            if (chToIdx.containsKey(s.charAt(i))) 
                minIdx = Math.max(chToIdx.get(s.charAt(i)) + 1, minIdx);
            maxLength = Math.max(maxLength, i - minIdx + 1);
            chToIdx.put(s.charAt(i), i);
        }
        return maxLength;
    }

  • 0
    D

    Hi, nice solution. But could you please explain why this is done

    minIdx = Math.max(chToIdx.get(s.charAt(i)) + 1, minIdx);

    I was doing this:
    minIdx = chToIdx.get(s.charAt(i)) + 1;
    and it is wrong. But I cant understand why?


  • 0
    S

    Hi, sorry for a delay with an answer. This is done, because the last index for our current char could be before the index of our last meeting of duplicate. For instance:
    "baabc", when we meet the second a our valid current prefix is just an "a", and when we meet the second "b" we need to consider only this "a" before it. In your case (without taking max) we would jump to the first "b" and the answer would be wrong.
    Hope it helps. :)


Log in to reply
 

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