Think of building a sentence by gluing words together one at a time versus writing every word on a sticky note first and then reading them off in one go. The second way is faster, and it's exactly the difference between slow and fast string code. String problems mix two skills you've already built, sliding windows and frequency counting, with the specifics of building strings efficiently and matching patterns inside them. This lesson closes out the strings arc with harder sliding-window variants, an anagram-detection pattern you'll reuse constantly, and a classic string-matching algorithm.

String building

In Python, strings are immutable. Every s += char creates a brand-new string, which makes naive concatenation in a loop O(n²) overall, since each of the n appends copies the whole string built so far.

"".join(list_of_strings) is the idiomatic O(n) pattern: it computes the final length once and allocates a single buffer, instead of reallocating on every append. This matters specifically when a problem asks you to build a result string inside a loop that could run thousands of times.

Remember: collect pieces in a list, then join once at the end. Never += a string inside a loop that could run many times.

Pattern matching

"Does string A appear inside string B" shows up disguised in many forms: substring search, anagram windows, repeated patterns. The naive approach checks every starting position in B against A character by character: O(n·m) where n = len(B), m = len(A). Two techniques improve on this:

1. Sliding window with frequency counts. When you're looking for anagrams or permutations of A within B, rather than an exact substring match, keep a frequency map of A and compare it against a same-size window's frequency map as it slides. This skips re-scanning m characters at every position.
2. Rabin-Karp (rolling hash). When you need exact substring matches, hash A once, then compute B's window hashes incrementally, an O(1) update per shift, instead of rehashing the whole window each time. Covered later in this lesson.

Remember: "does A's pattern appear anywhere in B" is either a sliding frequency-map comparison (for anagrams) or a rolling hash (for exact substrings). Both beat rescanning from scratch at every position.

Anagram detection

Two strings are anagrams if they contain exactly the same characters with the same multiplicities. The standard check: compare a Counter (or a fixed-size frequency array) of both strings.

For sliding-window anagram search (find every window of B that's an anagram of A), keep a running frequency count for the current window and compare it to A's frequency count incrementally instead of rebuilding it every shift:

Complexity: O(n) amortized if you avoid the O(26) Counter == Counter comparison per step. One optimization: track a running matches integer instead of comparing full Counters (see Find All Anagrams below for the fully optimized version). The version above is O(n · 26) worst case, still effectively linear since the alphabet is bounded.

Remember: two strings are anagrams exactly when their character counts match. Sliding that count window, instead of rebuilding it, is what makes the search fast.

Longest Substring with At Least K Repeating Characters

LeetCode 395 — String

Intuition: Any character appearing fewer than k times anywhere in the current substring can never be part of a valid answer: it disqualifies every substring that contains it. So find such a "bad" character, split the string at every occurrence of it, and recurse on each piece. This is divide-and-conquer, not sliding window, since the set of distinct characters and their positions don't slide cleanly here.

Approach: Count character frequencies in the current substring. If every frequency is at least k, the whole substring is valid, so return its length. Otherwise, split on the first character with frequency below k and recurse on each side, taking the max.

Complexity: Time O(n × 26) in the typical case: each recursion level does O(n) work, and the recursion depth is bounded by the 26-letter alphabet, since each split removes at least one distinct character entirely. Space O(n) for recursion and split copies.

Common mistakes: trying to force this into a sliding-window shape. The "at least K repeats" condition isn't monotonic in a way that supports a simple expand/contract two-pointer approach, which is why divide-and-conquer is the right tool here. Also, forgetting the base case len(s) < k, which would otherwise recurse forever on tiny fragments.

Remember: a character below the K-repeat threshold poisons every substring containing it. Split it out and recurse on the two clean halves.

Find All Anagrams in a String

LeetCode 438 — String

Intuition: Exactly the "sliding-window anagram search" pattern from the concept section: find every starting index in s where a fixed-size window is an anagram of p.

Approach: A fixed-size window of length len(p). Keep frequency counts and a matches counter, how many of the 26 letters currently have equal counts in both windows, to avoid comparing full frequency maps every shift: an O(1) per-step check instead of O(26).

Complexity: Time O(n × 26): the array comparison s_count == p_count is O(26), effectively O(1) since the alphabet is bounded, giving overall O(n). Space O(26) = O(1).

Common mistakes: comparing Counter objects every iteration without noticing the alphabet is a bounded constant. Still fine here since 26 is a constant, but worth explicitly noting to the interviewer that this is O(1) per check, not O(n). Also, an off-by-one on when the window becomes "full": i >= window_len - 1 is the first index at which a complete window exists.

Remember: a fixed-size window, two 26-slot count arrays, one array-equality check per shift. That's the whole algorithm.

Minimum Window Substring

LeetCode 76 — String — Review

Intuition: Find the smallest window in s containing every character of t, with at least their required counts. A classic variable-size sliding window: expand right until the window is valid (contains everything needed), then contract left as far as possible while it stays valid, recording the best window found.

Approach: Track required character counts from t. Expand right, decrementing a "still needed" counter whenever an added character helps satisfy a requirement. Once that counter hits 0 (window is valid), shrink left while validity holds, updating the best window at each fully-valid state.

Complexity: Time O(n + m) where n = len(s), m = len(t): each index enters and leaves the window at most once. Space O(m) for the need counter (bounded by the distinct characters in t).

Common mistakes: using need[ch] > 0 as the sole gate for decrementing missing correctly ignores characters not in t or already over-satisfied, but it's easy to instead decrement missing unconditionally, which breaks when duplicate or extra characters appear in the window. This is a genuinely hard sliding-window problem, worth revisiting the Sliding Window lessons' variable-window material if it doesn't come back quickly.

Remember: expand until valid, then shrink while still valid, recording the best window at every fully-valid moment. That expand/shrink rhythm is the whole trick.

Rabin-Karp Algorithm

LeetCode implement: String

Intuition: To find a pattern p inside text s, naive matching re-compares up to m characters at every one of n positions (O(n·m)). Rabin-Karp instead hashes the pattern once, then slides a window across s, updating the window's hash in O(1) per shift with a rolling hash formula, falling back to a full character comparison only when hashes match, to rule out hash collisions.

Approach: Compute the pattern's hash and the first window's hash using a polynomial rolling hash (base B, modulus M to bound the value size). At each shift, remove the leaving character's contribution and add the entering character's contribution in O(1). Compare hashes; on a match, verify with a direct substring comparison to handle the rare hash collision.

Complexity: Average time O(n + m): O(1) rolling update per shift, with occasional O(m) verification on hash matches, which is rare if MOD is large relative to collision risk. Worst case O(n·m) if many spurious hash collisions occur, mitigated by a large prime modulus. Space O(1) extra beyond the output.

Common mistakes: letting the hash grow unbounded without a modulus. That's fine in Python's arbitrary-precision integers, but it defeats the purpose of a fixed-size rolling hash and is wrong in most other languages, worth mentioning if portability comes up. Also, skipping the verification step after a hash match, which risks a false positive on a genuine collision. And getting the rolling-hash update formula's sign wrong when removing the leaving character: you must subtract leaving_char * BASE^(m-1) before re-multiplying by BASE, not after.

Remember: hash once, slide the hash in O(1) per step, and always verify a hash match with a real character comparison before trusting it.

Notice the shape common to Find All Anagrams, Minimum Window Substring, and Rabin-Karp: each replaces a per-position O(alphabet) or O(pattern-length) recheck with an O(1) incremental update, whether that's a match counter, a "missing" tally, or a rolling hash. That trade, recomputing nothing you can update instead, is the real skill this lesson teaches.