Problem intuition
- The naive version grows a substring from every starting point until a repeat appears.
- The optimal solution treats the substring as a sliding window and shrinks it only when a repeated character breaks validity.
Solution
The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.
Solution 1
Restart from every index
- Build a fresh set for every start index and extend until a duplicate appears.
- This is correct, but it revisits too much work.
- Time complexity: O(n^2)
- you restart the scan from every index and may revisit most characters for each start.
- Space complexity: O(min(n, charset))
- the set stores the distinct characters currently being tested in the substring.
Solution 2
Sliding window with character counts
- Expand the right edge of the window one character at a time.
- When the latest character becomes duplicated, move left until the window is valid again.
- Time complexity: O(n)
- both window pointers move forward through the string without backing up.
- Space complexity: O(min(n, charset))
- the map keeps counts for only the characters that appear in the current window.