Longest Substring Without Repeating Characters Explained: pwwkew & abba

Imagine you are given the string $s=\text{"pwwkew"}$ and asked to find the longest contiguous section of characters where no letter repeats. If you try the most obvious brute-force approach, you would list every possible substring, check each one for duplicates, and pick the longest. For short strings that sounds harmless, but as the length $n$ grows, checking every pair of start and end indices explodes into $\mathcal{O}(n^2)$ or even $\mathcal{O}(n^3)$ operations.

Now consider a slightly more devious input, $s=\text{"abba"}$. When scanning from left to right, your intuition might tell you to just start over or jump backward whenever you hit a duplicate character. But as we will see later, naive backward jumps cause you to miscalculate overlapping character windows and ruin your result.

We need a way to slide across the string in a single forward pass, dynamically adjusting our window boundaries without re-scanning characters we have already validated.

To find the longest substring without repeating characters in strings like "pwwkew" and "abba", we stop restarting from scratch at every index. We keep one window that is unique right now, and we slide it forward.

The window has two moving edges:
- right walks the string once, from index 0 to $n-1$. Each step tries to include $s[\text{right}]$.
- left only moves forward. When $s[\text{right}]$ is a duplicate that still sits inside the window, we jump left to one past that character's last index.

A hash map stores each character's last seen index. On each right:
1. Look up $j$, the last index of $s[\text{right}]$, if any.
2. If $j$ exists and $j\ge \text{left}$, the duplicate is still in the window, so set $\text{left}=j+1$. Never move left backward — that is the "abba" trap.
3. Record $s[\text{right}]\to \text{right}$ in the map.
4. Update $\text{max\_len}=\max (\text{max\_len},\text{right}-\text{left}+1)$.

On "pwwkew" the window grows to "wke" or "kew" (length 3). On "abba", after the two $b$s, left is already at the second $b$; the final $a$ must not pull left back to 0, so the answer stays 2, not 3.

To see how the left and right pointers interact with our character map, let's trace our two canonical test strings: s = "pwwkew" and s = "abba". We maintain a map storing the most recent index of each character, a left pointer starting at index 0, and a max_len accumulator.

- right = 0, char = p: map = {"p": 0}. left = 0. Window = "p" (len 1). max_len = 1.
- right = 1, char = w: map = {"p": 0, "w": 1}. left = 0. Window = "pw" (len 2). max_len = 2.
- right = 2, char = w: w is in map at index 1, and $1\ge \text{left}$ ($1\ge 0$). We jump left to $1+1=2$. map = {"p": 0, "w": 2}. Window = "w" (len 1). max_len = 2.
- right = 3, char = k: map = {"p": 0, "w": 2, "k": 3}. left = 2. Window = "wk" (len 2). max_len = 2.
- right = 4, char = e: map = {"p": 0, "w": 2, "k": 3, "e": 4}. left = 2. Window = "wke" (len 3). max_len = 3.
- right = 5, char = w: w is in map at index 2, and $2\ge \text{left}$ ($2\ge 2$). We jump left to $2+1=3$. map = {"p": 0, "w": 5, "k": 3, "e": 4}. Window = "kew" (len 3). max_len = 3.

- right = 0, char = a: map = {"a": 0}, left = 0, max_len = 1.
- right = 1, char = b: map = {"a": 0, "b": 1}, left = 0, max_len = 2.
- right = 2, char = b: b is at index 1 ($\ge \text{left}$). left jumps to $1+1=2$. map = {"a": 0, "b": 2}, left = 2. Window = "b" (len 1).
- right = 3, char = a: a is in the map at index 0. However, index 0 is strictly less than current left ($0<2$). Therefore, we ignore it and do not move left backward. left remains 2. Window = "ba" (len 2). max_len = 2.

Result for "pwwkew" is 3, and for "abba" is 2.

Now that you have seen how the left pointer leaps forward to $j+1$ rather than incrementing by one, it is time to test your mental model. Consider the string $s=\text{"abba"}$ which we analyzed in the previous phase. Imagine the scanning window has just processed the first two characters $\text{"ab"}$ (indices 0 and 1) and then encountered the first $\text{"b"}$ at index 2.

Before you look at the trace or write code for it, reason through what happens when the right pointer reaches the final character $\text{"a"}$ at index 3. Recall the core danger we established: the character $\text{’a’}$ was already seen at index 0, but our left pointer was already shifted past index 0 when we processed the duplicate $\text{"b"}$s.

Work through the following question to verify your understanding of how the character-index map prevents illegal backward slides.

string s = "abba";
// Assume right pointer is at index 3 (character 'a').
// What is the stored index of 'a' in your map, what is the current 'left' pointer value, 
// and why must 'left' NOT move backward to 0?

Now that you have traced how the sliding window and character index map process both $s=\text{"pwwkew"}$ and $s=\text{"abba"}$, you can transfer this exact mechanism to neighboring string problems. The core engine we built relies on a single right pointer expanding the boundary, a left pointer that only moves forward when a duplicate is found at or to the right of $\text{left}$, and an integer map storing the last seen indices. This $O(n)$ pattern reappears whenever you need to maintain a valid window state under character constraints.

Suppose you encounter a modified problem: finding the longest substring that contains at most two distinct characters, or finding the longest substring with repeating characters allowed up to $k$ replacements. While those problems require minor adjustments—such as keeping a frequency count instead of a last-seen index—the bounding logic remains identical. When designing an algorithmic solution for these variations, always check if your window contraction logic safely prevents the left pointer from retreating, preserving the strict invariant we established with $s=\text{"abba"}$.

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    # How would you adapt the character index or frequency map
    # to handle at most k distinct characters instead of all unique?
    pass