Longest Substring Without Repeating Characters

Solution: Using Sliding Window

Step 1

The current character is p add it to frequencyMap and compare the current window size with the frequencyMap size, both are equal which means no characters is repeating in the current window.

Update the maxLength to the current window size.

Let's continue to add more characters in the window.

Step 2

The current character is w add it to frequencyMap and compare the current window size with the frequencyMap size, both are equal which means no characters is repeating in the current window.

Update the maxLength to the current window size.

Let's continue to add more characters in the window.

Step 3

The current character is w add it to frequencyMap and compare the current window size with the frequencyMap size, both are not equal which means some character is repeating in the current window. And hence, this is an invalid window and therefore we need to fix this. Let's start shrinking this window until we get frequencyMap size equal to window size.

Step 4

After shrinking the window, the frequencyMap size is still not equal to window size. Hence shrink it again.

Step 5

After shrinking it again, we have got frequencyMap size equals to window size.

Now, try to update the maxLength, but the maxLength is already better than the current window size. So, it won't get updated. Let's continue to expand the window.

Step 6

The current character is k add it to frequencyMap and compare the current window size with the frequencyMap size, both are equal which means no characters is repeating in the current window.

Try to update the maxLength, but the maxLength is already better than the current window size. So, it won't get updated. Let's continue to expand the window.

Step 7

The current character is e add it to frequencyMap and compare the current window size with the frequencyMap size, both are equal which means no characters is repeating in the current window.

Update the maxLength to the current window size.

Let's continue to add more characters in the window.

Step 8

The current character is w add it to frequencyMap and compare the current window size with the frequencyMap size, both are not equal which means some character is repeating in the current window. And hence, this is an invalid window and therefore we need to fix this. Let's start shrinking this window until we get frequencyMap size equal to window size.

Step 9

After shrinking the window, we have got frequencyMap size equals to window size.

Now, try to update the maxLength, but the maxLength is already better than the current window size. So, it won't get updated. Let's continue to expand the window.

Step 10

The loop will be terminated as we don't have more elements to process.

Let's try to write code for the same.

Java Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int windowStart = 0;
        int maxLength = 0;
        Map<Character, Integer> frequencyMap = new HashMap<>();

        for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char ch = s.charAt(windowEnd); 
            frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
            while(frequencyMap.size() != (windowEnd - windowStart + 1)) {
                char leftChar = s.charAt(windowStart);
                frequencyMap.put(leftChar, frequencyMap.get(leftChar) - 1);
                if(frequencyMap.get(leftChar) == 0) {
                    frequencyMap.remove(leftChar);
                }
                windowStart += 1;
            }
            maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
        }
        return maxLength;
    }
}

C++ Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int windowStart = 0;
        int maxLength = 0;
        map<char, int> frequencyMap;

        for(int windowEnd = 0; windowEnd < s.size(); windowEnd++) {
            char ch = s[windowEnd]; 
            frequencyMap[ch]++;
            while(frequencyMap.size() != (windowEnd - windowStart + 1)) {
                char leftChar = s[windowStart];
                frequencyMap[leftChar]--;
                if(frequencyMap[leftChar] == 0) {
                    frequencyMap.erase(leftChar);
                }
                windowStart += 1;
            }
            maxLength = max(maxLength, windowEnd - windowStart + 1);
        }
        return maxLength;
    }
};

Python Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        windowStart = 0
        maxLength = 0
        frequencyMap = dict()

        for windowEnd in range(len(s)):
            ch = s[windowEnd]
            frequencyMap[ch] = frequencyMap.get(ch, 0) + 1
            while len(frequencyMap) != (windowEnd - windowStart + 1):
                leftChar = s[windowStart]
                frequencyMap[leftChar] -= 1
                if frequencyMap[leftChar] == 0:
                    del frequencyMap[leftChar]
                windowStart += 1
            maxLength = max(maxLength, windowEnd - windowStart + 1)
        
        return maxLength

Time Complexity: O(N), where N is the size of the string s.
Space Complexity: O(1), though we have used a map but in the worst case scenario we end up storing only 26 alphabets which is a constant.