3 - Longest Substring Without Repeating Characters

Problem

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

Input: s = "abcabcbb"
Output: 3
Explanation: the answer is "abc", with the length of 3

Input: s = "bbbbb"
Output: 1
Explanation: the answer is "b", with the length of 1

Input: s = "pwwkew"
Output: 3
Explanation: the answer is "wke", with the length of 3

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces

Approach

Unlike 567, the window here doesn’t have a set size. Keep two ends, l and r, and a count of how many times each character is inside the window. Move r forward one character at a time and add it. If that character now shows up twice, move l forward, removing characters, until the repeat is gone. After that the window has no repeats, so check its length against the best so far. Both ends only ever move forward, so each character is added once and removed at most once.

The count array has 128 slots so it covers every character s can contain, not just lowercase letters.

s = "abcabcbb"
r=0 [a]                         best=1
r=1 [ab]                        best=2
r=2 [abc]                       best=3
r=3 [abca] -> shrink -> [bca]   best=3
r=4 [bcab] -> shrink -> [cab]   best=3
r=5 [cabc] -> shrink -> [abc]   best=3
r=6 [abcb] -> shrink -> [cb]    best=3
r=7 [cbb]  -> shrink -> [b]     best=3
answer = 3

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int c[128] = {0};
        int l = 0, best = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            c[s[r]]++;
            while (c[s[r]] > 1) {
                c[s[l]]--;
                l++;
            }
            best = max(best, r - l + 1);
        }
        return best;
    }
};

• time: O(n)
• space: O(1) - a fixed array of 128 counts