Java: Longest substring without repeating characters

Intuition

Imagine you have two pointers, let's call them left and right. These pointers define a "window" or a substring within your main string s.

We start with an empty window (both left and right pointers at the beginning of the string).

We expand the window by moving the right pointer forward, character by character.

As we expand, we keep track of the characters currently inside our window.

If we encounter a character that is already in our window, we have a duplicate! To fix this, we must shrink the window from the left by moving the left pointer forward until the duplicate character is removed.

At every step of expansion, the window contains a substring with no duplicates. We simply keep track of the largest window size we've seen so far.

This way, we only have to pass through the string once with our pointers, making it very efficient.

Approach

Pseudo Code:

Initialization:

1. Initialize left = 0.
2. Initialize maxLength = 0.
3. Initialize an empty Set called charSet.

Iteration:

1. Loop through the string with the right pointer, from the beginning to the end.
2. Core Logic (Inside the Loop):
3. For the character at the right pointer, s[right]:
4. Check for Duplicates: Check if s[right] is already in charSet.
5. If it is, you have a duplicate. You need to shrink the window from the left.
6. Start a while loop that continues as long as s[right] is in charSet.
7. Inside the while loop: remove the character s[left] from charSet and increment left.
8. Expand the Window: After the while loop finishes (meaning the duplicate is gone), add the current character s[right] to charSet. This officially adds it to your window.
9. Update Max Length: Your current window is valid (no duplicates). Its length is right - left + 1. Compare this length with maxLength and update maxLength if it's greater.
10. maxLength = max(maxLength, right - left + 1)

Final Result:

After the main loop finishes, maxLength will hold the length of the longest substring without any duplicate characters. Return maxLength.

Complexity

• Time complexity: O(n) where n is number of characters in the given string
• Space complexity: O(k) where k is number of unique characters in the given string

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {

        if(s == null || s.length() == 0)
            return 0;
        
        int left = 0;
        int maxLength = 0;
        Set<Character> charSet = new HashSet<>();

        for (int right = 0; right < s.length(); right++){
            
            char currentChar = s.charAt(right);

            while (charSet.contains(currentChar)){
                char charLeft = s.charAt(left);
                charSet.remove(charLeft);
                left = left + 1;
            }

            charSet.add(currentChar);

            int currentLength = right - left + 1;
            maxLength = Math.max(maxLength, currentLength);
        }

        return maxLength;
        
    }
}