Longest Substring Without Repeating Characters

How it works

Instead of removing characters one by one when we see a repeat, we can jump the left pointer directly to the correct position. We keep a map that stores the last index where each character appeared. When a character repeats, the earliest valid starting point moves to one position after its previous occurrence. This lets us adjust the window in one step and always keep it valid, making the approach fast and clean.

Steps

1. Create a map mp to store the last index of each character.
2. Initialize:
   • l = 0 for the start of the window,
   • res = 0 for the longest length.
3. Loop through the string with index r:
   • If s[r] is already in mp, move l to mp[s[r]] + 1, but never backward.
   • Update mp[s[r]] = r.
   • Update the longest length: res = max(res, r - l + 1).
4. Return res at the end.

Complexity

• Time complexity: O(n)
• Space complexity: O(m)

Where n is the length of the string and m is the total number of unique characters in the string.

Things to watch for

Not Taking the Maximum When Jumping the Left Pointer

In the optimal sliding window approach, when you find a duplicate character, you should move the left pointer to max(left, lastIndex[char] + 1). Forgetting the max operation can cause the left pointer to move backwards if the duplicate character's last occurrence is before the current window start, leading to incorrect results.

Forgetting to Update the Character's Last Index

After processing each character, you must update its last seen index in the map, regardless of whether it was a duplicate. Failing to update the index means future duplicate checks will reference stale positions, causing incorrect window calculations.

Off-by-One in Window Size Calculation

When calculating the substring length, ensure you use right - left + 1 since both indices are inclusive. Using right - left will undercount the length by one, resulting in an answer that is consistently one less than correct.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {}
        l = 0
        res = 0

        for r in range(len(s)):
            if s[r] in mp:
                l = max(mp[s[r]] + 1, l)
            mp[s[r]] = r
            res = max(res, r - l + 1)
        return res

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int l = 0, res = 0;

        for (int r = 0; r < s.size(); r++) {
            if (mp.find(s[r]) != mp.end()) {
                l = max(mp[s[r]] + 1, l);
            }
            mp[s[r]] = r;
            res = max(res, r - l + 1);
        }
        return res;
    }
};