The longest Substring without Repeating Characters

I’m starting out on LeetCode, and am currently working on the problem Longest Substring Without Repeating Characters.

Given a string s, find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

I feel like my approach should work, but for some reason it fails certain tests (see below). Could someone help me understand why?

public int lengthOfLongestSubstring(String s) {
        int current_max = 0; 
        HashMap<Character, Character> seen_values = new HashMap(s.length()); 
        
        int running_count = 0; 
        
        for (int i = 0; i < s.length(); i++){
            if (seen_values.containsKey(s.charAt(i))){
                running_count = 1; 
                seen_values = new HashMap(s.length());
                seen_values.put(s.charAt(i), s.charAt(i));
            } else {
                running_count++;
                if (running_count > current_max){
                    current_max = running_count; 
                }
                seen_values.put(s.charAt(i), s.charAt(i));
            }
        }
        return current_max;
    }

Failed Test

Input:

"abac"

The code produces output 2, but expected 3.

This is the only case that I’ve been able to create where it fails.
Could anyone explain why does it happen?

Answer

You’re considering the case when a repeated character has been encountered as the start of a new substring. That’s incorrect.

Let’s consider the following example:

"abcbdef"

The longest substring without repeated characters would be "cbdef".

Iteration progresses from substring "a" to "ab" and then to "abc". At this moment, we encounter the second character 'b'. Instead of considering it as a start of a new substring, we have to move the beginning of the previous substring past the first occurrence of 'b', i.e. substring should start from 'c' (not from the second 'b').

To implement this logic, instead of maintaining the counter you need to track the starting index of the current substring (as well as maximum substring length).

And instead of HashMap you can use HashSet as @Dawood ibn Kareem has already pointed out in the comments.

While iterating, you need to offer each character to the set, and if method add() returns false the logic for moving the starting index of the substring needs to be executed. I.e. you need to move the index in the nested loop past the first occurrence of the current character, and note that every character encountered in the nested loop has to be removed from the set (apart from the current character).

This approach could be enhanced.

As @greybeard has suggested, we skip the step of removing the characters between the previous and new starting position by storing the index of each encountered character in the Map and checking not only whether the next character exists but also if the value associated with it is greater or equal to the current starting index.

That how it can be implemented:

public static int lengthOfLongestSubstring(String str) {
    Map<Character, Integer> charToIndex = new HashMap<>(str.length());
    int maxLength = 0;
    int start = 0;
    
    for (int end = 0; end < str.length(); end++) {
        char next = str.charAt(end);
        if (charToIndex.containsKey(next) && charToIndex.get(next) >= start) {
            start = charToIndex.get(next) + 1;
        }
        charToIndex.put(next, end);
        maxLength = Math.max(maxLength,  end - start + 1);
    }
    return maxLength;
}

main()

public static void main(String[] args) {
    System.out.println(lengthOfLongestSubstring("abcbdef"));
    System.out.println(lengthOfLongestSubstring("abac"));
}

Output:

5   // "cbdef"
3   // "bac"