Longest String Without Repeating Characters

Longest Substring Without Repeating Characters

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

Sliding Window Solution

This problem uses the sliding window technique with a hash map, similar to the approach in Two Sum and Valid Anagram.

Two pointers define the window boundaries:

• left: the start of the current valid substring
• right: iterates through the string

When a repeating character is encountered, the left pointer advances past the previous occurrence of that character, ensuring the window always contains unique characters.

 
#include <string>
#include <unordered_map>
using namespace std;
 
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> lastSeen;
        int left = 0, longest = 0;
 
        for (int right = 0; right < s.size(); right++) {
            if (lastSeen.count(s[right]) && lastSeen[s[right]] >= left) {
                // Move left boundary past the duplicate
                left = lastSeen[s[right]] + 1;
            }
            lastSeen[s[right]] = right;
            longest = max(longest, right - left + 1);
        }
        return longest;
    }
};