The challenge
Return the length of the longest contiguous substring in which every character appears at most once.
Strings contain ASCII characters; indices are zero-based. C++17 or later.
Example
abcabcbb → 3, from abc; abba → 2.
Use the walkthrough below to inspect the input and each state change.
See No repeats, step by step
Expand, shrink, and inspect the window state.
8 elements · zero-based indices
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 25
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
0
View exact input
Input: ["a","b","c","a","b","c","b","b"]
Current window is empty.
Put it into code
Before adding right, the old window is valid. Only the incoming character can introduce a duplicate, so shrink until its frequency is one.
Indices are zero-based. C++ uses C++17 or later.
def longest_unique(s):
count = {}
left = best = 0
for right, char in enumerate(s):
count[char] = count.get(char, 0) + 1
while count[char] > 1:
old = s[left]
count[old] -= 1
if count[old] == 0:
del count[old]
left += 1
best = max(best, right - left + 1)
return best#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int longest_unique(const string& s) {
array<int, 256> count{}; // ASCII input.
int left = 0, best = 0;
for (int r = 0; r < (int)s.size(); ++r) {
unsigned char c = s[r];
++count[c];
while (count[c] > 1) --count[(unsigned char)s[left++]];
best = max(best, r - left + 1);
}
return best;
}