Longest substring: definition
A substring is a contiguous part of a string. Find the longest one whose characters are all distinct, and return its length. This is a problem solved with the sliding-window technique.
Task example: Longest Substring Without Repeating Characters
Given a string s, return the length of its longest substring without repeated characters. Keep spaces, punctuation, and letter case. Do not skip or rearrange characters.
For abcabcbb, abc is one longest valid substring of length 3. For pwwkew, wke has length 3; pwke is not valid because its characters are not contiguous.
Brute force: video explanation
s = "abcabcbb" → 3
Prefer reading? Follow the steps below.
- Choose left as the starting index. Create a fresh set, then move right and add characters that are not in the set.
- After each addition, update best with right - left + 1. At a repeated character, stop this inner loop: extending it cannot remove the repeat.
- Try the next start with an empty set. For abcabcbb, starts 0, 1, and 2 each reach length 3. Check the remaining starts and return 3.
Time complexity · O(n²)
Up to n starts each scan up to n characters. With average O(1) set operations, the worst-case time is O(n²).
Space complexity · O(n)
The set stores only distinct characters: O(min(n, alphabet size)) extra space, bounded by O(n). A fixed alphabet bounds the set independently of n.
Sliding window: video explanation
s = "abcabcbb" → 3
Prefer reading? Follow the steps below.
- Keep a set for the current window and start left at 0. Move right forward one character at a time.
- While the incoming character is already in the set, remove s[left] and advance left. Use while, not if: more than one removal may be needed.
- Add s[right], then update best with right - left + 1. For abcabcbb, the b at index 6 requires removing both a and the old b. Return the best length, 3.
Why it works: after shrinking, the window contains no repeats. Each right endpoint is considered with the longest valid window ending there. Reusing the set avoids rescanning every start.
Time complexity · O(n)
Each character enters the set once and leaves at most once. Both pointers move forward, so total work is O(n), assuming average O(1) set operations.
Space complexity · O(n)
The set stores only distinct characters: O(min(n, alphabet size)) extra space, bounded by O(n). A fixed alphabet bounds the set independently of n.