DSA sheet · Strings · Sliding Window pattern

Longest Substring Without Repeating Characters

This is the teacher's second string question in the sliding window pattern, and she solves it three times, each one faster than the last. First a brute force with two loops and a set. Then a sliding window with a frequency map, where the left pointer shrinks one step at a time inside a while loop. Finally an optimal version where the map stores the last index of each character, so the left pointer can jump straight past the duplicate.

Why it matters: this is the classic "longest valid window" problem. Once you understand why the nested while is still O(n) and not O(n²), you understand every variable-size sliding window. She also says this is exactly the explanation most people get wrong in interviews.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (sliding window from scratch)
• Part A · Brute force: every start, grow until a repeat (set)
• Part B · Sliding window with a frequency map (shrink in a while loop)
• Part C · Optimal: store the last index and jump left
• Part D · Revision page

Part 0 · Before starting

Substring = a contiguous piece

A substring is a piece of the string where the characters sit next to each other (contiguous). You pick a start index and an end index and take everything between them. You can't skip characters. (For arrays the same idea is called a subarray.)

A string of length n has n·(n+1)/2 non-empty substrings. For n = 8 that's 36.

Brute force over all windows, and why it repeats work

The simplest way to answer any "best substring" question is to try every start i, and for each start, every end j. That's two nested loops, so O(n²) windows. The waste: when the start moves from i to i+1, the next loop re-reads characters i+1, i+2, … that the previous loop already checked. Sliding window keeps that knowledge instead of throwing it away.

The window [left..right]

A window is the current substring we're looking at, from index left to index right (both included). Its length is right − left + 1. Two moves change it:

• Expand: move right one step to the right. One new character comes in.
• Shrink: move left one step to the right. One old character goes out.

The teacher's rule: right always expands, left always shrinks, and whatever right did, left undoes. If right added a character to the map, left removes it (lowers its count) when it leaves. Neither pointer ever moves backwards.

Fixed-size vs variable-size windows

Three kinds of answers

There's one more trick for "exactly K" counts: exactly(K) = atMost(K) − atMost(K−1). This page doesn't need it.

Why sliding window needs a "monotonic" rule

Sliding window only works if the rule behaves the same way every time: making the window bigger can only make it "worse", and making it smaller can only make it "better". Here the rule is "no repeated character". If a window has a repeat, any bigger window that contains it still has that repeat. If a window has no repeat, any smaller piece of it also has none. So it's safe to shrink from the left until the repeat is gone, and we never need to move left backwards.

Counter-example from sum problems: with negative numbers, adding a number can make the sum smaller, so "too big → shrink" is no longer safe. That's why sum-type sliding windows need non-negative numbers.

Set vs frequency map (Counter)

• A set only answers "is x inside?". Fine when each character appears at most once.
• A frequency map (dict, or collections.Counter) stores how many times each character is in the window. Add: freq[c] = freq.get(c, 0) + 1. Remove: lower the count, and delete the key when it hits 0.
• A last-index map stores where each character was last seen: last[c] = i. Part C uses this.

def longest_valid(s, add, remove, is_bad):
    left = 0
    best = 0
    for right in range(len(s)):
        add(s[right])                  # expand: right brings a char in
        while is_bad():                # window broke the rule
            remove(s[left])            # shrink: left undoes what right did
            left += 1
        best = max(best, right - left + 1)   # window is valid again
    return best

Part A · Brute force: every start, grow until a repeat

LeetCode 3

1The question in simple words

You get a string s. Find the length of the longest substring in which every character is different (no character appears twice).

"abc" has 3 different characters. Add the next "a" and you get "abca", where a appears twice, so that's not allowed. No valid substring is longer than 3. The teacher's example is exactly this one: "abcabcbb" → 3. Other LeetCode examples: "bbbbb" → 1, "pwwkew" → 3 ("wke"; "pwke" doesn't count because it's not contiguous).

2What the constraints tell us

• 0 ≤ length ≤ 5·10⁴. Length 0 is allowed. For an empty string the answer is simply 0, and the code must not crash.
• n = 5·10⁴ → a true O(n²) would be 25·10⁸ steps, well past the ~10⁸ safe line, so it would give TLE. Keep that in mind for the brute force.
• The string holds English letters, digits, symbols and spaces. So the number of different characters is small (a fixed alphabet). That fact rescues the brute force, as we'll see.

The teacher reads constraints to decide two things: does an O(n²) idea pass, and which pattern to reach for when optimising.

3Intuition: every start, and stop at the first repeat

Put a finger i on a start index. A second finger j starts at i and walks right, making the substrings s[i..i], s[i..i+1], s[i..i+2], …. All of them start at i.

But we don't need to walk j to the very end. The moment j reads a character that's already inside the current substring, this substring is broken, and every longer one starting at i contains the same repeat, so it's broken too. So we stop j at the first repeat, then move i one step and start again.

4Building the logic from the example

i = 0

Substrings starting at 0: "a", "ab", "abc", "abca", …. j reads a → b → c, all new. Then j reads a at index 3, but a is already in "abc". Stop. The best from i = 0 is "abc", length 3.

i = 1

Start j at 1 again: "b", "bc", "bca" are all fine, then "bcab" repeats b. Stop. Best from here is 3 again.

i = 2, 3, … until the last index

i = 2: "c", "ca", "cab", then "cabc" repeats c → 3. And so on. Since the window size is not fixed, i goes all the way to the last index. The biggest length seen anywhere is the answer: 3.

How do we measure the length?

While the substring s[i..j] is still valid, its length is j − i + 1. We update best right after adding s[j] to the set. When j hits a repeat, we break before updating, so the broken length is never recorded. The last valid length (one step earlier) was already saved.

5Approach steps

1. best = 0.
2. For each start i: make an empty set.
3. For j from i to the end: read c = s[j].
4. If c is in the set → repeat → break.
5. Else add c, and do best = max(best, j − i + 1).
6. Return best.

6Code (Python)

class Solution:
    def lengthOfLongestSubstring(self, s):
        n = len(s)
        best = 0
        for i in range(n):              # start of the substring
            seen = set()                # fresh set for this start
            for j in range(i, n):       # end of the substring
                c = s[j]
                if c in seen:           # repeat found
                    break               # every longer one is broken too
                seen.add(c)
                best = max(best, j - i + 1)
        return best

7Code line by line

8Dry run (hand table)

s = "abcabcbb". Each row is one start i. j walks right until a repeat.

Final answer: 3 ✓

9Complexity & remember

• At first sight it's two nested loops → O(n²), which for n = 5·10⁴ means 25·10⁸ steps → TLE.
• But look closer, as the teacher does. The inner loop can only take as many steps as there are different characters before it must hit a repeat. With 26 letters, a substring of 27 characters must repeat one. So the inner loop runs at most about 26 times, and the total is O(26·n), which is linear. That's why her submission passed (slowly).
• Space O(26) (the alphabet size) for the set.

Part B · Sliding window with a frequency map

1The question again, with the new goal

Same question. The new goal: one pass of the right pointer, and no going back to re-check characters we already know are unique.

2What the constraints tell us now

• Brute force is O(26·n), which is linear, but it's still slow. Why optimise something that's already linear? The teacher's reason: wherever you see repeated work, there's something to optimise.
• The empty string must still return 0.

3Intuition: where is the repeated work?

In the brute force, i = 0 found "abc" is all unique. Then i moved to 1 and j re-checked b and c, which we already knew were unique. That re-check of (length found − 1) characters happens at every start. That's the waste.

The fix: keep the window. When a repeat comes in on the right, don't throw the whole window away. Just push the left edge forward until the repeat is gone. Everything still inside is known to be unique, so we don't check it again.

4Building the logic from examples

Expanding

left = right = 0. Every time right moves, the new character goes into a frequency map (character → how many times it's in the window). Note: it's added because of right, not left. a → {a:1}, b → {a:1, b:1}, c → {a:1, b:1, c:1}. All counts are 1, so the window "abc" is valid. Length = right − left + 1 = 3.

The repeat arrives

right moves to index 3, which is 'a'. Now {a:2, b:1, c:1}. A count above 1 means a repeat, so the window "abca" is invalid. The last valid window was one step earlier, with length right − left = 3 (not +1, because the right end itself is the bad character). In the code we do the same thing a cleaner way: shrink first, then measure with right − left + 1.

Shrinking

Now left undoes what right did: look at s[left], lower its count, and move left one step. s[0] = 'a' → a goes from 2 to 1 → left = 1. Now a's count is 1 again, so the window "bca" is valid.

Why while, not if?

The character at left is not always the repeated one. The teacher's example: imagine the window was "deabc" and then another 'a' comes in. Removing d doesn't fix it. Removing e doesn't fix it either. Only after removing the old a is the window valid. So we keep shrinking while the new character's count is still above 1.

5Approach steps

1. freq = {}, left = 0, best = 0.
2. For each right: add s[right] to freq (count + 1).
3. While freq[s[right]] > 1: lower the count of s[left] (delete it at 0), left += 1.
4. Now the window is valid: best = max(best, right − left + 1).
5. Return best.

6Code (Python)

class Solution:
    def lengthOfLongestSubstring(self, s):
        freq = {}                         # char -> count inside the window
        left = 0
        best = 0
        for right in range(len(s)):
            c = s[right]
            freq[c] = freq.get(c, 0) + 1  # expand: right brings c in
            while freq[c] > 1:            # c is repeated -> shrink
                out = s[left]
                freq[out] -= 1            # left undoes right's work
                if freq[out] == 0:
                    del freq[out]
                left += 1
            best = max(best, right - left + 1)   # valid window
        return best

7Code line by line

8Dry run (hand table)

s = "abcabcbb".

Step 7 is where the while earns its place: the first character to leave ('a') is not the repeated one.

Final answer: 3 ✓

9Complexity & remember: why the nested while is NOT O(n²)

The teacher spends a lot of time on this, because a while inside a for looks like n².

Her example: s = "abcdeefgh…". right walks a, b, c, d, e with no shrinking at all. Then the second e arrives, and left walks all the way from a to the second e, about n steps at once. Then right continues with no shrinking again. If later "…jkll" appears, left walks again, but it continues from where it stopped. It never starts over.

• right visits each index once → n steps in total.
• left also visits each index at most once over the whole run → at most n steps in total, not n per right.
• Total ≤ n + n = O(2n) = O(n). The work is added, not multiplied. O(n²) would need left to re-walk the window for every right, and it never does.
• Space O(alphabet) for the map.

Her submission passed, but it was still not the fastest. The extra n comes from the while loop. Can we make each shrink O(1)? That's Part C.

Part C · Optimal: store the last index, jump left

1The question again, with the new goal

Same question. Goal: remove the shrinking while loop so the whole thing is exactly one pass, O(n).

2What the constraints tell us

Nothing new. The O(2n) version already passes. This is about doing it in the cleanest, fastest way, which is the one interviewers expect at the end.

3Intuition: why walk when you can jump?

In Part B, when the second 'e' arrives, left walks step by step looking for the old 'e'. But what if we already knew where the old e was? Then we could put left directly one step after the old e, in O(1).

So instead of storing counts, the map stores the last index where each character was seen.

4Building the logic, and one important fix

The teacher's rule

• Read c = s[right].
• If c is in the map, the old copy is at last[c] → move left = last[c] + 1.
• Store the current position: last[c] = right.
• best = max(best, right − left + 1).

5Approach steps

1. last = {}, left = 0, best = 0.
2. For each right, c = s[right]:
3. If c is in last: left = max(left, last[c] + 1).
4. last[c] = right (always).
5. best = max(best, right − left + 1).
6. Return best.

6Code (Python)

class Solution:
    def lengthOfLongestSubstring(self, s):
        last = {}                         # char -> last index seen
        left = 0
        best = 0
        for right in range(len(s)):
            c = s[right]
            if c in last:
                left = max(left, last[c] + 1)   # jump past the old copy
            last[c] = right                     # always store the newest index
            best = max(best, right - left + 1)
        return best

7Code line by line

8Dry run (hand table)

s = "abcabcbb".

And the "abba" case that needs the max:

9Complexity & remember

• Time O(n), exactly one pass. Each step is O(1) dict work, with no inner loop. Her submission was the fastest of the three.
• Space O(alphabet) for the map.

Part D · Revision page

s = Solution()
print(s.lengthOfLongestSubstring("abcabcbb"))   # 3
print(s.lengthOfLongestSubstring("bbbbb"))      # 1
print(s.lengthOfLongestSubstring("pwwkew"))     # 3
print(s.lengthOfLongestSubstring(""))           # 0
print(s.lengthOfLongestSubstring("abba"))       # 2
print(s.lengthOfLongestSubstring("abcdeefgh"))  # 5

Based on this video: Longest Substring Without Repeating Characters | Sliding Window