DSA sheet · Strings · Sliding Window pattern

Longest Substring with K Unique Characters

This is the next string question in the sliding window pattern. The teacher first writes a brute force (every start, a set, stop when there are too many different characters). Then she optimises it with a sliding window, and on the way she explains three choices that come up in many string problems: why a set is not enough, why a frequency map works, and when a plain array of size 26 is better than a hash map.

Why it matters: "longest window with at most / exactly K different things" is a very common shape (Fruits Into Baskets is the same problem with K = 2). The key habit from this video is "delete the key when its count hits 0", because the size of the map is the number of different characters.

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 + a set
• Part B · Sliding window with a frequency map
• Part C · Same window with an array of 26 (faster)
• 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. You choose a start and an end and take everything in between, with no skipping. (In arrays it's called a subarray.) A string of length n has n·(n+1)/2 non-empty substrings.

"Unique" or "distinct" characters

The number of unique (distinct) characters in a substring is how many different letters it has, however many times each one appears. "aabac" has 5 characters but only 3 distinct ones: a, b, c.

Brute force over all windows, and why it repeats work

Try every start i, and for each start every end j: two loops, O(n²) windows. When i moves one step, the inner loop re-reads characters that the previous round already looked at. Sliding window keeps what it learned instead.

The window [left..right], expanding and shrinking

The window is the current substring s[left..right]; its length is right − left + 1. The teacher's two phases:

• Expansion: right moves forward, and the new character is added (its count goes up).
• Shrinking: left moves forward, and the character at left is removed (its count goes down).

Whatever right does, left undoes. Neither pointer ever goes back.

Fixed-size vs variable-size windows

Longest vs shortest vs count

For "count of subarrays with exactly K distinct", the trick is exactly(K) = atMost(K) − atMost(K−1) (Subarrays with K Different Integers). For "longest with exactly K", like here, we don't need it: we just record the length only when the window has exactly K.

Why sliding window works here (the monotonic rule)

Adding a character can only keep or raise the number of distinct characters. Removing one can only keep or lower it. So once the window has more than K distinct, every bigger window starting at the same left also has more than K. It's safe to shrink from the left, and left never needs to go back. (In sum problems, this kind of rule fails when numbers can be negative.)

Set vs frequency map vs count array

• set: knows which characters are inside, but not how many of each. Removing one copy of 'a' would wrongly forget all the a's.
• frequency map (dict or collections.Counter): character → count. Add: +1. Remove: −1, and delete the key at 0. Then len(freq) = number of distinct characters in the window.
• array of 26: count[ord(c) − ord('a')]. Same idea, no hashing. Part C uses it.

def longest_valid(s, add, remove, too_big, is_answer):
    left = 0
    best = -1
    for right in range(len(s)):
        add(s[right])                  # expand
        while too_big():               # rule broken -> shrink
            remove(s[left])            # left undoes right
            left += 1
        if is_answer():                # window qualifies
            best = max(best, right - left + 1)
    return best

Part A · Brute force: every start + a set

GeeksforGeeks · Longest K unique characters substring

1The question in simple words

You get a string s of lower-case letters and a number k. Find the length of the longest substring that has exactly k distinct characters. If there is no such substring, return −1.

"cbebebe" uses only c, b, e: exactly 3 distinct, and nothing longer has exactly 3. Another small case: s = "aaaa", k = 2 → −1 (only one distinct letter exists).

The teacher asks: why does the question say only lower-case letters? Keep it in mind. It's the reason an array of size 26 works (Part C).

2What the constraints tell us

• length up to 10⁵. O(n²) = 10¹⁰ steps, far beyond the ~10⁸ safe line → brute force will give TLE. We'll still write it first, then optimise.
• 1 ≤ k ≤ 26. Only 26 lower-case letters, so k can't be more than 26 in a meaningful way.
• "No such substring" → −1, so the answer must start at −1, not 0.

3Intuition: every start, stop once there are too many letters

Fix a start i. Move j from i to the right, and keep the letters of s[i..j] in a set (a set keeps only unique things, so its size = number of distinct letters).

• set size < k → not enough different letters yet, keep going.
• set size == k → valid! Record j − i + 1, and keep going (a longer one might still have exactly k).
• set size > k → too many, and growing can never bring it back down → break, move i.

4Building the logic from the example

i = 0

"a" → 1 distinct, not valid. "aa" → still 1 (the set doesn't add a again). "aab" → 2. "aaba" → still 2. "aabac" → 3 ✓, length 5. Save it.

"aabacbe" → e is new → size 4 > 3. From now on, every longer substring starting at 0 has at least 4 distinct letters. Break. Best so far: 6.

i = 1

New empty set, since the old one belonged to start 0. "a", "ab", "aba" (2), "abac" (3 ✓, length 4, not better than 6), "abacb" (3 ✓, 5), "abacbe" (4) → break.

Continue for every i

Doing this for every start, the biggest valid length shows up at i = 4: "cbebebe", length 7, which runs to the end of the string with only c, b, e.

5Approach steps

1. best = −1 (in case nothing is valid).
2. For each start i: new empty set.
3. For j from i to the end: add s[j] to the set.
4. If size == k → best = max(best, j − i + 1).
5. If size > k → break.
6. Return best.

6Code (Python)

class Solution:
    def longestKSubstr(self, s, k):
        n = len(s)
        best = -1                        # -1 if no valid substring
        for i in range(n):
            seen = set()                 # distinct letters of s[i..j]
            for j in range(i, n):
                seen.add(s[j])
                if len(seen) == k:
                    best = max(best, j - i + 1)
                elif len(seen) > k:
                    break                # can only get worse
        return best

7Code line by line

8Dry run (hand table)

s = "aabacbebebe", k = 3. Each row is one start i.

Final answer: 7 ✓

9Complexity & remember

• Time O(n²): two nested loops. With n = 10⁵ that's 10¹⁰ → her submission got TLE, as expected.
• Space O(26) for the set.

Part B · Sliding window with a frequency map

1The question again, with the new goal

Same question, but in about one pass: O(n), so 10⁵ is easy.

2What the constraints tell us now

• n = 10⁵ → we need O(n) or O(n log n).
• Only lower-case letters → at most 26 keys in the map (and Part C's array idea).

3Intuition: where is the repeated work?

From i = 0 we already learned that s[0..5] has 3 or fewer distinct letters. When i moves to 1, the brute force reads s[1..5] all over again, even though we already know every piece inside it also has ≤ 3 distinct letters. That re-reading is the waste. Sliding window keeps the window and only fixes its left edge.

4Building the logic from examples

First try: use a set (and watch it fail)

The teacher first tries the window with a plain set:

• right adds a, a (no change), b, a (no change), c → size 3, window "aabac", length 5. Then b → still 3, length 6.
• right adds e → size 4. Too many, so we shrink. left is at index 0, 'a'. Remove 'a' from the set → size 3, and left moves to index 1.
• The set now says "3 distinct, valid". But the window s[1..6] = "abacbe" still contains a (at indexes 1 and 3)! It really has 4 distinct letters.

The set forgot that there were three a's. Removing one copy shouldn't remove the letter. We need to keep removing until every a has left the window. So we need to know how many of each letter are inside → a frequency map.

The frequency map

Map: letter → how many times it's in the window. At "aabacbe" it is {a:3, b:2, c:1, e:1}. The number of distinct letters is the number of keys: 4.

• Right adds: count + 1.
• Left undoes it: count − 1 (not "remove the letter").

Shrinking until valid: a while loop

With 4 keys > k = 3, shrink:

1. left = 0, 'a': a 3 → 2. Still 4 keys. left = 1.
2. left = 1, 'a': a 2 → 1. Still 4 keys. left = 2.
3. left = 2, 'b': b 2 → 1. Still 4 keys. left = 3.
4. left = 3, 'a': a 1 → 0. left = 4. But the map still shows 4 keys, because a is there with value 0!

When do we record the answer?

After the shrinking, the window has at most k distinct letters. It might have fewer (at the start, "aab" has only 2). The question wants exactly k, so we record right − left + 1 only if len(freq) == k.

After "cbe", right keeps going: b, e, b, e. No new letters, so no shrinking, and the window grows to "cbebebe" = length 7. That's the answer.

5Approach steps

1. freq = {}, left = 0, best = −1.
2. For each right: freq[s[right]] += 1.
3. While len(freq) > k: lower freq[s[left]], delete it if 0, left += 1.
4. If len(freq) == k: best = max(best, right − left + 1).
5. Return best.

6Code (Python)

class Solution:
    def longestKSubstr(self, s, k):
        if k <= 0:                       # constraints say k >= 1; just a guard
            return -1
        freq = {}                        # letter -> count in window
        left = 0
        best = -1
        for right in range(len(s)):
            c = s[right]
            freq[c] = freq.get(c, 0) + 1          # expand
            while len(freq) > k:                  # too many distinct
                out = s[left]
                freq[out] -= 1                    # left undoes right
                if freq[out] == 0:
                    del freq[out]                 # 0 must not count as a key
                left += 1
            if len(freq) == k:                    # exactly k -> candidate
                best = max(best, right - left + 1)
        return best

7Code line by line

8Dry run (hand table)

s = "aabacbebebe", k = 3.

Final answer: 7 ✓

9Complexity & remember

A while inside a for looks like n², but it isn't:

• right goes from 0 to n−1 once. It never comes back and restarts.
• left also only moves forward. It continues from where it stopped, so over the whole run it moves at most n times.
• Total ≤ n + n = O(2n) = O(n). The teacher puts it as "more than n, less than 2n".
• Space O(26): at most k + 1 keys in the map.

Her submission passed, but the speed was only average (about 40%). Her reason: the hash map does extra hashing work on every update.

Part C · Same window with an array of 26

1What's the same and what changes

The window logic is exactly Part B. Only the storage changes: a list of 26 counts instead of a dict. The question said "only lower-case letters", and that's why this works.

2How can an array store letter counts?

Use the letter's code to get an index. ord('a') is 97. So ord(c) − ord('a') gives a → 0, b → 98 − 97 = 1, …, z → 25. count[0] holds a's count, count[1] holds b's, and so on.

An array has no "number of keys", so we keep our own counter distinct: +1 when a count goes 0 → 1, −1 when it goes 1 → 0. (That's the array version of "delete the key at 0".)

3When to use an array and when a map (her rule)

Both are correct here. The array is just faster.

4Code (Python)

class Solution:
    def longestKSubstr(self, s, k):
        if k <= 0:
            return -1
        count = [0] * 26                 # count[0] = a, ..., count[25] = z
        distinct = 0                     # letters with count > 0
        left = 0
        best = -1
        for right in range(len(s)):
            i = ord(s[right]) - ord('a')
            if count[i] == 0:
                distinct += 1            # a new letter enters
            count[i] += 1
            while distinct > k:
                j = ord(s[left]) - ord('a')
                count[j] -= 1
                if count[j] == 0:
                    distinct -= 1        # that letter fully left
                left += 1
            if distinct == k:
                best = max(best, right - left + 1)
        return best

5Code line by line (only the new lines)

6Dry run & complexity

The steps are identical to Part B's table: distinct follows the number of keys column (1, 1, 2, 2, 3, 3, 4 → shrink back to 3, then 3 to the end), and the answer is again 7. Time O(n), space O(26), but each step is cheaper than a dict operation.

Part D · Revision page

s = Solution()
print(s.longestKSubstr("aabacbebebe", 3))   # 7
print(s.longestKSubstr("aaaa", 2))          # -1
print(s.longestKSubstr("aaaa", 1))          # 4
print(s.longestKSubstr("abc", 3))           # 3
print(s.longestKSubstr("abc", 4))           # -1
print(s.longestKSubstr("a", 1))             # 1

Based on this video: Longest Substring with K Unique Characters | Sliding Window