Coding Drills · 03

Strings & Sliding Window

A string is just a char[] with opinions. Almost every string interview question collapses into one of six scanning shapes: a stack that matches pairs, a window [L, R] that grows and shrinks, a center that expands outward, a run scanner, a pattern matcher that never backs up, or digit-by-digit arithmetic. Drills 24–32 build each shape from scratch in Java.

Drills

Easy

Medium

Hard

01 Arrays & Hashing · 02 Two Pointers · 03 Strings & Window · 04 Binary Search · 05 Linked Lists · 06 Trees · 07 Grids · 08 Graphs · 09 DP · 10 Backtracking

Chapter One · Core Idea

Scanning a String Without Rescanning It

The brute-force instinct on a string of length n is to enumerate every substring — there are n(n+1)/2 of them — and test each one. That is O(n²) substrings and often O(n³) work once you test them. Every technique on this page exists to avoid that. The trick is always the same: carry state forward so that the work done for position i is reused for position i + 1. A stack remembers which brackets are still open. A window remembers the counts of everything between L and R. KMP remembers how much of the pattern is already matched. Each one turns "start over" into "adjust a little".

The sliding window — one pass, two monotonic pointers

Analogy: Reading a long line of text through a cardboard frame with adjustable edges. You never lift the frame and restart from the left — you only slide the right edge forward to reveal more, and slide the left edge forward to hide what you no longer need. Whatever you are counting (distinct letters, missing letters, repeated letters) is updated by the one character that entered or the one that left, never recounted from scratch.

🧱

Stack matching

Last opened must be first closed. Drill 24.

🪟

Variable window

Grow R, shrink L while a counter says "invalid". Drills 25, 26, 27.

🎯

Expand around center

2n − 1 centers, grow outward while mirrored. Drill 28.

🔁

Run scanning

Consume a run of equal chars, emit (char, count). Drills 29, 31.

🔍

Pattern matching

KMP's failure table means the text pointer never moves back. Drill 30.

✖️

Digit simulation

Grade-school arithmetic on char digits with carries. Drill 32.

Chapter Two · Mental Model

How String Problems Think

Brackets close in the reverse order they open

▶

The most recent unmatched opener is the only legal partner for the next closer — exactly what a stack's top gives you in O(1)

The question says "longest / shortest contiguous substring such that…"

▶

The constraint is monotonic in the window: adding characters can only break "at most K" constraints and only help "contains all of T" constraints — so one pointer per direction suffices

A frequency array or map is updated by exactly one character per pointer move

▶

Validity checks become O(1) (a size, a counter, a max) instead of re-scanning the window — the window algorithm stays O(n)

A palindrome is symmetric around its middle

▶

Pick the middle first (a character or a gap), then grow outward while both ends match — 2n − 1 centers, O(n²) total, O(1) memory

The output describes runs of equal characters

▶

An inner while loop consumes a whole run; the outer loop handles one run per iteration — no off-by-one "last group" flush needed

Numbers are too big for long, so they arrive as strings

▶

Simulate pencil-and-paper arithmetic: digit i times digit j always lands in positions i + j and i + j + 1

Read the constraint, not the story:

"Contiguous" plus "longest" or "shortest" is the sliding-window signal. "Subsequence" is not — that is dynamic programming (page 09).
"Only uppercase English letters" or "ASCII" is a hint to use an int[26] or int[128] instead of a HashMap — same big-O, far smaller constant.
"Return the new length, modify in place" means a read/write pointer pair, exactly like the two-pointer compaction on page 02.

Chapter Three · Pattern Toolkit

Three Templates You Will Reuse

Memorise these three skeletons. Each drill below is one of them with a different validity test plugged in. The skill an interviewer is checking is not typing the loop — it is choosing the right counter so that "is the window valid?" costs O(1).

Template 1 — Longest Valid Window

Grow R every step. While the window breaks the rule, shrink L. After the inner loop the window is valid, so record its length.

Pseudocode

function longestValid(s):
  L = 0, best = 0, state = empty
  for R = 0 to n - 1:
      add(state, s[R])                 // expand
      while invalid(state):
          remove(state, s[L]); L++      // shrink until legal again
      best = max(best, R - L + 1)        // window is valid here
  return best                            // O(n): L and R each move n times
  

Template 1 on "abcabcbb" — longest substring without repeats

Template 2 — Shortest Covering Window

The mirror image of Template 1: grow R until the window becomes valid, then shrink L as far as it stays valid, recording the length before each shrink.

Pseudocode

function shortestValid(s):
  L = 0, best = ∞
  for R = 0 to n - 1:
      add(state, s[R])
      while valid(state):                   // note: VALID, not invalid
          best = min(best, R - L + 1)      // record BEFORE shrinking
          remove(state, s[L]); L++
  return best
  

The two phases alternate — each pointer still moves at most n times

Template 3 — Expand Around Center

Every palindrome has a center: a single character (odd length) or the gap between two characters (even length). Try all 2n − 1 centers and grow outward while the ends match.

Pseudocode

function expand(s, lo, hi):
  while lo >= 0 and hi < n and s[lo] == s[hi]:
      lo--, hi++
  return hi - lo - 1                     // both overshot by one

for i = 0 to n - 1:
  best = max(best, expand(s, i, i), expand(s, i, i + 1))
  

"abba" has 7 centers — the even center between the two b's wins

Drill 24 · Stack

Valid Parentheses

🏷️

Difficulty

Easy

🔗

LeetCode

LC 20 · full write-up

🧩

Pattern

stack

Given a string containing only the characters ( ) [ ] { }, decide whether it is valid: every opener is closed by the same type of bracket, and brackets close in the correct order (the most recently opened one closes first).

Example

Input:  s = "({[]})"     Output: true
Input:  s = "([)]"       Output: false   // ']' must close before ')'
Input:  s = "(("         Output: false   // openers left over

Key insight: Nesting is last-in, first-out. Think of Russian dolls: you can only close the innermost open doll. So when you see an opener, push the closer you now expect; when you see a closer, it must equal whatever is on top. Pushing the expected closer (instead of the opener) turns three separate if checks into one equality test.

Brute force → optimal. A naive approach repeatedly deletes adjacent pairs (), [], {} until nothing changes; each pass is O(n) and there can be n/2 passes, so O(n²). The stack does the same "cancel the innermost pair" work in a single left-to-right pass: every character is pushed or popped exactly once, O(n).

Trace on "({[]})" — the stack holds expected closers

Java — ArrayDeque stack, push the expected closer

import java.util.ArrayDeque;
import java.util.Deque;

public class ValidParentheses {

  public static boolean isValid(String s) {
      if (s.length() % 2 == 1) return false;           // odd length can never balance
      Deque<Character> stack = new ArrayDeque<>();     // faster than legacy Stack
      for (char c : s.toCharArray()) {
          if (c == '(') stack.push(')');               // push the EXPECTED closer
          else if (c == '{') stack.push('}');
          else if (c == '[') stack.push(']');
          else if (stack.isEmpty() || stack.pop() != c) return false;
      }
      return stack.isEmpty();                          // leftovers = unclosed openers
  }

  public static void main(String[] args) {
      System.out.println(isValid("({[]})"));  // true
      System.out.println(isValid("([)]"));    // false
      System.out.println(isValid("(("));      // false
  }
}

Approach	Time	Space	Note
Repeatedly delete "()", "[]", "{}"	O(n²)	O(n)	New string per pass
Stack (one pass)	O(n)	O(n)	Worst case "((((((" fills the stack

Common bugs:

Popping without checking isEmpty() first — input ")" throws NoSuchElementException on ArrayDeque (or EmptyStackException on Stack).
Returning true at the end of the loop instead of stack.isEmpty() — "((" would wrongly pass.
Using java.util.Stack: it works, but it is synchronized and extends Vector. ArrayDeque is the recommended stack.
Odd length is an instant false — a free early exit, not a correctness requirement.

Drill 25 · Sliding Window

Longest Substring with At Most K Distinct Characters

🏷️

Difficulty

Medium

🔗

LeetCode

LC 340 (premium)

🧩

Pattern

sliding window hash map

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Example

Input:  s = "eceba", k = 2
Output: 3        // "ece" uses only 'e' and 'c'
Input:  s = "aa", k = 1
Output: 2

Key insight: "Distinct characters in the window" is exactly map.size() if the map drops a key when its count reaches zero. So validity is an O(1) check — map.size() <= k — and the problem is Template 1 verbatim.

Brute force → optimal. Checking all O(n²) substrings and counting distinct characters in each is O(n³), or O(n²) if you extend each start incrementally. The window improves on that by noticing that if s[L..R] has more than k distinct characters, so does every longer window starting at L — so L can be abandoned forever. Both pointers only move right: O(n).

Trace on "eceba", k = 2 — green = window after shrinking, red = evicted this step

Java — HashMap counts, drop keys at zero

import java.util.HashMap;
import java.util.Map;

public class LongestKDistinct {

  public static int lengthOfLongestSubstringKDistinct(String s, int k) {
      if (k == 0) return 0;
      Map<Character, Integer> freq = new HashMap<>();
      int best = 0, left = 0;
      for (int right = 0; right < s.length(); right++) {
          freq.merge(s.charAt(right), 1, Integer::sum);       // expand
          while (freq.size() > k) {                           // too many distinct: shrink
              char out = s.charAt(left++);
              if (freq.merge(out, -1, Integer::sum) == 0) freq.remove(out);
          }
          best = Math.max(best, right - left + 1);            // window is valid here
      }
      return best;
  }

  public static void main(String[] args) {
      System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3  ("ece")
      System.out.println(lengthOfLongestSubstringKDistinct("aa", 1));    // 2
  }
}

Approach	Time	Space	Note
All substrings, count distinct	O(n²)	O(k)	Extend each start incrementally
Sliding window + map	O(n)	O(k)	Map never holds more than k + 1 keys

Common bugs:

Decrementing the count but forgetting map.remove(key) at zero — map.size() then counts ghosts and the window shrinks too far.
Using if instead of while for the shrink: one eviction may not be enough (R=3 above needed two).
k == 0 must return 0; without the guard the loop still works here, but many variants divide by or index with k.
Comparing boxed Integer counts with == — fine below 128 because of the cache, silently wrong above it. merge(...) == 0 is safe because it unboxes against an int literal.

Drill 26 · Sliding Window

Longest Repeating Character Replacement

🏷️

Difficulty

Medium

🔗

LeetCode

LC 424 · full write-up

🧩

Pattern

sliding window int[26]

Given an uppercase string s and an integer k, you may change at most k characters to any other uppercase letter. Return the length of the longest substring that can be made of one repeated letter.

Example

Input:  s = "AABABBA", k = 1
Output: 4        // "AABA" → change the B → "AAAA"
Input:  s = "ABAB", k = 2
Output: 4        // change both B's (or both A's)

Key insight: In any window, the cheapest repaint keeps the most frequent letter and repaints everything else. So a window is valid when length − maxFreq ≤ k. You never need to know which letter wins — only how many times it appears.

Brute force → optimal. Trying every substring and computing its majority count is O(26·n²). The window version tracks counts in an int[26]. The subtle optimisation: maxFreq is never decreased when L moves. A stale (too large) maxFreq can only make the window look valid when it is not — but the window then merely slides (L and R both +1) instead of growing, so best can only increase when a genuinely higher frequency appears. That makes the shrink a single if, not a while.

Walkthrough — "AABABBA", k = 1

R	char	window after step	maxFreq	len − maxFreq	action	best
0	A	A	1	0	grow	1
1	A	AA	2	0	grow	2
2	B	AAB	2	1	grow (1 ≤ k)	3
3	A	AABA	3	1	grow	4
4	B	ABAB	3	5 − 3 = 2 > 1	slide: drop s[0], L=1	4
5	B	BABB	3	5 − 3 = 2 > 1	slide: drop s[1], L=2	4
6	A	ABBA	3	5 − 3 = 2 > 1	slide: drop s[2], L=3	4

The "len" in the check is the length before sliding (R − L + 1 = 5). After the last slide the window is "ABBA", whose true maximum is 2 — yet maxFreq still reads 3. That stale value is harmless: it could only let a window of width 4 pass, and 4 was already recorded. The answer can only grow when some letter genuinely reaches a count of 4.

Java — int[26] counts, sliding (non-shrinking) window

public class CharacterReplacement {

  public static int characterReplacement(String s, int k) {
      int[] count = new int[26];
      int maxFreq = 0, best = 0, left = 0;
      for (int right = 0; right < s.length(); right++) {
          maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
          // cells to repaint = window length - most frequent letter
          if (right - left + 1 - maxFreq > k) {
              count[s.charAt(left) - 'A']--;
              left++;                                   // slide, never shrink below best
          }
          best = Math.max(best, right - left + 1);
      }
      return best;
  }

  public static void main(String[] args) {
      System.out.println(characterReplacement("AABABBA", 1)); // 4  ("AABA" or "ABBB")
      System.out.println(characterReplacement("ABAB", 2));    // 4
  }
}

Approach	Time	Space	Note
Every substring, recount	O(26 · n²)	O(1)	Too slow for n = 10⁵
Window, recompute max over 26 letters	O(26 · n)	O(1)	Correct, simpler to argue
Window, stale maxFreq	O(n)	O(1)	Alphabet size is constant

Common bugs:

Indexing count[c - 'a'] on an uppercase-only input — negative index, ArrayIndexOutOfBoundsException.
"Fixing" the stale maxFreq by decrementing it when L moves — it then under-counts and the window shrinks wrongly. Either leave it stale or recompute it from all 26 counts.
Answer can never exceed n; with k ≥ n the whole string is the answer — the loop handles it without a special case.

Drill 27 · Sliding Window

Minimum Window Substring

🏷️

Difficulty

Hard

🔗

LeetCode

LC 76 · full write-up

🧩

Pattern

shortest window missing counter

Given strings s and t, return the shortest substring of s that contains every character of t including duplicates. If there is none, return the empty string.

Example

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Input:  s = "a", t = "aa"
Output: ""          // t needs two a's, s has one

Key insight: Keep one array need[c] = how many more of c the window still owes, and one integer missing = total owed. Adding s[R] pays a debt only if need[s[R]] was positive; removing s[L] creates a debt only if need[s[L]] becomes positive. The window covers t exactly when missing == 0 — an O(1) test instead of comparing two maps.

Brute force → optimal. Testing every substring against t's counts is O(n² · |Σ|). Template 2 cuts it to one pass: expand R until missing hits 0, then shrink L while it stays 0, recording each candidate. Characters not in t go negative in need, which is exactly what lets them be dropped for free later.

The three moments that matter on s = "ADOBECODEBANC", t = "ABC"

Every valid window the inner loop sees

R	L range while valid	windows recorded / checked	why the shrink stops
5	0	"ADOBEC" (6) → best 6	dropping A at 0 owes an A
10	1 → 5	"DOBECODEBA" … "CODEBA" (all ≥ 6)	dropping C at 5 owes a C
12	6 → 9	"ODEBANC" (7), "DEBANC" (6), "EBANC" (5) → best 5, "BANC" (4) → best 4	dropping B at 9 owes a B

Java — need[] array + missing counter

public class MinWindowSubstring {

  public static String minWindow(String s, String t) {
      if (t.isEmpty() || s.length() < t.length()) return "";
      int[] need = new int[128];
      for (char c : t.toCharArray()) need[c]++;
      int missing = t.length();                 // chars of t still not covered
      int bestLen = Integer.MAX_VALUE, bestStart = 0, left = 0;

      for (int right = 0; right < s.length(); right++) {
          if (need[s.charAt(right)]-- > 0) missing--;     // a useful char entered
          while (missing == 0) {                           // window covers t: shrink
              if (right - left + 1 < bestLen) {
                  bestLen = right - left + 1;
                  bestStart = left;
              }
              if (++need[s.charAt(left++)] > 0) missing++; // lost a needed char
          }
      }
      return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
  }

  public static void main(String[] args) {
      System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC
      System.out.println(minWindow("a", "aa"));              // "" (not enough a's)
  }
}

Approach	Time	Space	Note
Every substring vs t's counts	O(n² · \|Σ\|)	O(\|Σ\|)	Σ = alphabet
Window with two HashMaps	O(\|s\| + \|t\|)	O(\|Σ\|)	Boxing overhead, Integer equality traps
Window, int[128] + missing	O(\|s\| + \|t\|)	O(1)	128 ints regardless of input

Common bugs:

Counting distinct characters of t instead of total characters — t = "AA" needs two A's, not one.
Comparing window.get(c) == tMap.get(c) with two Integer objects — breaks once a count passes 127. Use .intValue() or primitive arrays.
Recording the best window after shrinking — you record a window that is no longer valid.
Storing the substring on every improvement — O(n) copy each time. Store bestStart and bestLen, cut once at the end.

Drill 28 · Expand Around Center

Longest Palindromic Substring

🏷️

Difficulty

Medium

🔗

LeetCode

LC 5 · full write-up

🧩

Pattern

expand around center

Given a string s, return its longest substring that reads the same forwards and backwards. If several have the same maximum length, any one of them is accepted.

Example

Input:  s = "babad"     Output: "bab"    // "aba" is also accepted
Input:  s = "cbbd"      Output: "bb"     // even-length: needs the gap center

Key insight: Checking a substring for palindrome-ness from the outside in wastes work. Growing from the inside out reuses it: if s[lo+1..hi-1] is a palindrome, then s[lo..hi] is one exactly when s[lo] == s[hi]. One comparison per extra character.

Brute force → optimal. Checking all O(n²) substrings with an O(n) palindrome test is O(n³). Expand-around-center is O(n²) time and O(1) space and is what interviewers expect. A DP table dp[i][j] is also O(n²) but uses O(n²) memory. Manacher's algorithm reaches O(n) — worth naming, rarely worth coding in an interview.

Expanding every center of "babad"

Java — expand around 2n − 1 centers

public class LongestPalindrome {

  public static String longestPalindrome(String s) {
      if (s.length() < 2) return s;
      int start = 0, maxLen = 1;
      for (int i = 0; i < s.length(); i++) {
          int odd  = expand(s, i, i);          // center on a character
          int even = expand(s, i, i + 1);      // center between two characters
          int len = Math.max(odd, even);
          if (len > maxLen) {
              maxLen = len;
              start = i - (len - 1) / 2;       // works for both odd and even
          }
      }
      return s.substring(start, start + maxLen);
  }

  private static int expand(String s, int lo, int hi) {
      while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
          lo--;
          hi++;
      }
      return hi - lo - 1;                      // length of the last valid palindrome
  }

  public static void main(String[] args) {
      System.out.println(longestPalindrome("babad")); // bab
      System.out.println(longestPalindrome("cbbd"));  // bb
  }
}

Approach	Time	Space	Note
All substrings + check	O(n³)	O(1)	Too slow beyond n ≈ 300
DP table dp[i][j]	O(n²)	O(n²)	1000 × 1000 booleans = 1 MB
Expand around center	O(n²)	O(1)	Interview standard
Manacher	O(n)	O(n)	Reuses mirror radii; rarely expected

Common bugs:

Only expanding odd centers — "cbbd" returns "c" instead of "bb".
Returning hi - lo + 1 from expand: both pointers have already stepped one past the palindrome, so the length is hi - lo - 1.
Start index for even lengths: i - len / 2 is off by one for even len; i - (len - 1) / 2 works for both parities.
Building substrings inside the loop — track start and maxLen and call substring once.

Drill 29 · Run Scan + Read/Write

String Compression

🏷️

Difficulty

Medium

🔗

LeetCode

LC 443

🧩

Pattern

run scan read/write pointers

Compress a char[] in place: each maximal run of a repeated character becomes the character followed by its count — but the count is written only when the run is longer than 1, and a count like 12 is written as two characters '1','2'. Return the new length; only the first that many cells matter.

Example

Input:  chars = ['a','a','b','b','c','c','c']
Output: 6      // chars starts with ['a','2','b','2','c','3']
Input:  chars = ['a','b','b','b','b','b','b','b','b','b','b','b','b']
Output: 4      // "ab12" — a single 'a' gets no count

Key insight: The compressed form of a run is never longer than the run itself (a run of 1 writes 1 char; a run of length L ≥ 2 writes 1 + digits(L) ≤ L chars). So the write pointer can never overtake the read pointer, and writing into the same array is safe — the same read/write compaction you used for Move Zeroes on page 02.

Brute force → optimal. The easy version builds a StringBuilder and copies it back: O(n) time but O(n) extra space, which violates the in-place requirement. The optimal version keeps a read index that consumes one whole run per outer iteration and a write index that emits the character and (if needed) the digits. Consuming the run with an inner while avoids the classic "flush the last group after the loop" bug.

Walkthrough — ['a','a','b','b','c','c','c']

run	char	read: start → end	length	written	write after
1	a	0 → 2	2	'a', '2'	2
2	b	2 → 4	2	'b', '2'	4
3	c	4 → 7	3	'c', '3'	6

After run 1 the array is ['a','2','b','b','c','c','c'] — the write landed on cells read has already passed. Final return value: 6.

Java — consume a run, emit char + digits

import java.util.Arrays;

public class StringCompression {

  public static int compress(char[] chars) {
      int write = 0, read = 0;
      while (read < chars.length) {
          char c = chars[read];
          int runStart = read;
          while (read < chars.length && chars[read] == c) read++;   // consume the run
          chars[write++] = c;
          int runLen = read - runStart;
          if (runLen > 1) {                                         // count only if > 1
              for (char d : Integer.toString(runLen).toCharArray()) chars[write++] = d;
          }
      }
      return write;
  }

  public static void main(String[] args) {
      char[] chars = {'a', 'a', 'b', 'b', 'c', 'c', 'c'};
      int len = compress(chars);
      System.out.println(len);                                      // 6
      System.out.println(Arrays.toString(Arrays.copyOf(chars, len))); // [a, 2, b, 2, c, 3]

      char[] single = {'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'};
      len = compress(single);
      System.out.println(new String(single, 0, len));               // ab12
  }
}

Approach	Time	Space	Note
StringBuilder then copy back	O(n)	O(n)	Not in place
Read/write in place	O(n)	O(1)	Count digits are at most 4 for n ≤ 2000

Common bugs (including one in the original version of this drill):

Writing a count of 1 — the problem writes "a2bc3", not "a2b1c3". For ['a','a','b','c','c','c'] the correct answer is 5, not 6.
Writing a two-digit count as one char: (char) ('0' + 12) is '<'. Convert with Integer.toString(runLen) and copy each digit.
Forgetting import java.util.Arrays when printing with Arrays.toString — a compile error, not a runtime one.
Returning chars.length instead of write.

Drill 30 · Pattern Matching

Implement strStr() — Brute Force and KMP

🏷️

Difficulty

Easy

🔗

LeetCode

LC 28

🧩

Pattern

fixed window KMP

Return the index of the first occurrence of needle in haystack, or -1 if it does not occur. This is what String.indexOf does — the drill is to write it yourself.

Example

Input:  haystack = "hello", needle = "ll"                Output: 2
Input:  haystack = "abxabcabcaby", needle = "abcaby"     Output: 6
Input:  haystack = "aaaaa", needle = "bba"               Output: -1

Key insight: When a match fails after j characters, you already know those j characters of the haystack — they equal needle[0..j-1]. KMP precomputes, for every prefix of the needle, the longest proper prefix that is also a suffix (lps). On a mismatch you keep that overlap and continue, so the haystack index never moves backwards.

Brute force → optimal. Sliding a fixed window of length m and comparing character by character is O((n − m + 1) · m) — fine for most inputs, but "aaaa…ab" in "aaaa…aaab" degrades to O(n·m). KMP is O(n + m): building lps is O(m), and the scan is O(n) because j can only decrease as many times as it increased. In an interview, write the brute force first, state its worst case, then offer KMP.

KMP on haystack "abxabcabcaby", needle "abcaby"

Java — brute force and KMP side by side

public class StrStr {

  // Brute force: try every alignment. O((n - m + 1) * m)
  public static int strStrBrute(String haystack, String needle) {
      int n = haystack.length(), m = needle.length();
      for (int i = 0; i + m <= n; i++) {
          int j = 0;
          while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
          if (j == m) return i;
      }
      return -1;
  }

  // KMP: never move the haystack pointer backwards. O(n + m)
  public static int strStr(String haystack, String needle) {
      int m = needle.length();
      if (m == 0) return 0;
      int[] lps = buildLps(needle);
      int j = 0;                                        // chars of needle matched
      for (int i = 0; i < haystack.length(); i++) {
          while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = lps[j - 1];
          if (haystack.charAt(i) == needle.charAt(j)) j++;
          if (j == m) return i - m + 1;
      }
      return -1;
  }

  // lps[i] = length of the longest proper prefix of needle[0..i] that is also a suffix
  private static int[] buildLps(String p) {
      int[] lps = new int[p.length()];
      int len = 0;
      for (int i = 1; i < p.length(); i++) {
          while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
          if (p.charAt(i) == p.charAt(len)) len++;
          lps[i] = len;
      }
      return lps;
  }

  public static void main(String[] args) {
      System.out.println(strStrBrute("hello", "ll"));           // 2
      System.out.println(strStr("hello", "ll"));                // 2
      System.out.println(strStr("abxabcabcaby", "abcaby"));     // 6
      System.out.println(strStr("aaaaa", "bba"));               // -1
  }
}

Approach	Time	Space	Note
Brute force window	O((n − m + 1) · m)	O(1)	Usually fast; worst case O(n·m)
KMP	O(n + m)	O(m)	lps array; text pointer never backs up
Rabin–Karp rolling hash	O(n + m) expected	O(1)	Needs a collision check on hash match

Common bugs:

Loop bound i < n - m misses a match that ends at the last character — use i + m <= n (also safe when m > n).
Empty needle: by convention the answer is 0 (matches String.indexOf("")).
In KMP, using if instead of while for the fallback j = lps[j - 1] — one fallback may not be enough.
The complexity claim "O(n·m)" for the brute force is the worst case, not the typical case — say both.

Drill 31 · Run Scan

Count and Say

🏷️

Difficulty

Medium

🔗

LeetCode

LC 38

🧩

Pattern

run-length encoding simulation

The count-and-say sequence starts with "1". Each next term is produced by reading the previous term aloud, run by run: "21" is read "one 2, one 1" and becomes "1211". Return the n-th term.

Example

Input:  n = 4
Output: "1211"
// 1 → "1" · 2 → "11" · 3 → "21" · 4 → "1211" · 5 → "111221"

Key insight: Each step is run-length encoding with the order flipped to (count, digit). It is the same inner-while run scanner as Drill 29, just emitting into a new StringBuilder instead of overwriting in place.

Brute force → optimal. There is no shortcut formula — you must build every term. The recursive version (countAndSay(n - 1) then encode) is correct but uses O(n) stack frames for no benefit; the loop is simpler. What matters for the complexity claim is how long the terms get: they grow by roughly 30% per step (Conway's constant λ ≈ 1.3036), not by doubling. Term 30 — LeetCode's maximum — has 4,462 characters.

Walkthrough — reading each term aloud

n	previous term	runs	said as	new term
2	1	[1]	one 1	11
3	11	[11]	two 1s	21
4	21	[2] [1]	one 2, one 1	1211
5	1211	[1] [2] [11]	one 1, one 2, two 1s	111221
6	111221	[111] [22] [1]	three 1s, two 2s, one 1	312211

Java — iterative run-length "say"

public class CountAndSay {

  public static String countAndSay(int n) {
      String term = "1";
      for (int step = 2; step <= n; step++) {
          StringBuilder next = new StringBuilder();
          int i = 0;
          while (i < term.length()) {
              char digit = term.charAt(i);
              int run = 0;
              while (i < term.length() && term.charAt(i) == digit) {
                  i++;
                  run++;
              }
              next.append(run).append(digit);   // "say" the run: count then digit
          }
          term = next.toString();
      }
      return term;
  }

  public static void main(String[] args) {
      for (int n = 1; n <= 5; n++) System.out.println(n + " -> " + countAndSay(n));
      // 1 -> 1, 2 -> 11, 3 -> 21, 4 -> 1211, 5 -> 111221
  }
}

Approach	Time	Space	Note
Recursive build	O(L₁ + … + Lₙ)	O(Lₙ + n)	Extra n stack frames
Iterative build	O(L₁ + … + Lₙ) ≈ O(1.31ⁿ)	O(Lₙ)	Lₙ = length of term n

Common bugs:

Claiming O(2ⁿ) — the original version of this drill did. Terms grow by about 1.3036× per step, so O(2ⁿ) is a loose upper bound, not the real cost.
Appending digit then count ("12" for one 2 written as "21") — the count comes first.
A "compare with next" loop that forgets to flush the final run. The inner-while form has no final flush to forget.
String concatenation s += ... in the loop is O(L²) per term — use StringBuilder.

Drill 32 · Digit Simulation

Multiply Strings

🏷️

Difficulty

Medium

🔗

LeetCode

LC 43

🧩

Pattern

grade-school math position array

Given two non-negative integers num1 and num2 as strings, return their product as a string. You may not convert the inputs to integers directly or use BigInteger — the inputs can be 200 digits long.

Example

Input:  num1 = "123", num2 = "456"
Output: "56088"
Input:  num1 = "0", num2 = "52"
Output: "0"

Key insight: An m-digit number times an n-digit number has at most m + n digits. Digit num1[i] times digit num2[j] contributes to exactly two positions of that result: its ones digit lands in pos[i + j + 1] and its carry in pos[i + j]. So you can accumulate every partial product directly, instead of building n shifted rows and adding them.

Brute force → optimal. The schoolbook method — multiply num1 by each digit of num2, shift, then add the rows with a string-addition helper — is also O(m·n) but allocates n intermediate strings. The position-array version does the same arithmetic in one int[m + n]. (Karatsuba gets O(n^1.585) for huge numbers; not expected here.)

Where 2 × 6 lands in "123" × "456"

All nine digit products, right to left

i, j	digits	product	slots	pos after
2, 2	3 × 6	18	4, 5	[0,0,0,0,1,8]
2, 1	3 × 5	15	3, 4	[0,0,0,1,6,8]
2, 0	3 × 4	12	2, 3	[0,0,1,3,6,8]
1, 2	2 × 6	12	3, 4	[0,0,1,4,8,8]
1, 1	2 × 5	10	2, 3	[0,0,2,4,8,8]
1, 0	2 × 4	8	1, 2	[0,1,0,4,8,8]
0, 2	1 × 6	6	2, 3	[0,1,1,0,8,8]
0, 1	1 × 5	5	1, 2	[0,1,6,0,8,8]
0, 0	1 × 4	4	0, 1	[0,5,6,0,8,8]

Java — accumulate into pos[i + j] and pos[i + j + 1]

public class MultiplyStrings {

  public static String multiply(String num1, String num2) {
      if (num1.equals("0") || num2.equals("0")) return "0";
      int m = num1.length(), n = num2.length();
      int[] pos = new int[m + n];                       // product has at most m + n digits
      for (int i = m - 1; i >= 0; i--) {
          for (int j = n - 1; j >= 0; j--) {
              int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
              int sum = mul + pos[i + j + 1];           // add onto the ones slot
              pos[i + j + 1] = sum % 10;
              pos[i + j] += sum / 10;                   // carry into the tens slot
          }
      }
      StringBuilder sb = new StringBuilder();
      for (int d : pos) {
          if (sb.length() == 0 && d == 0) continue;     // skip leading zeros
          sb.append(d);
      }
      return sb.toString();
  }

  public static void main(String[] args) {
      System.out.println(multiply("123", "456")); // 56088
      System.out.println(multiply("99", "99"));   // 9801
      System.out.println(multiply("0", "52"));    // 0
  }
}

Approach	Time	Space	Note
Shifted rows + string addition	O(m · n)	O(m · n)	n intermediate strings
Position array	O(m · n)	O(m + n)	One int array, one StringBuilder

Common bugs:

Forgetting to add the existing pos[i + j + 1] before taking % 10 — partial products overwrite each other.
Leaving leading zeros: pos[0] is 0 whenever the product has fewer than m + n digits.
Returning "" for "0" × "52" — the early return (or the empty-builder fallback) must produce "0".
Parsing with Long.parseLong — overflows past 19 digits and is explicitly disallowed.

Chapter Thirteen · Summary

All Nine Drills at a Glance

#	Drill	Pattern	Time	Space	Difficulty
24	Valid Parentheses	Stack of expected closers	O(n)	O(n)	Easy
25	Longest Substring, ≤ K Distinct	Longest window + map	O(n)	O(k)	Medium
26	Longest Repeating Char Replacement	Window, len − maxFreq ≤ k	O(n)	O(1)	Medium
27	Minimum Window Substring	Shortest window + missing counter	O(\|s\| + \|t\|)	O(1)	Hard
28	Longest Palindromic Substring	Expand around 2n − 1 centers	O(n²)	O(1)	Medium
29	String Compression	Run scan + read/write	O(n)	O(1)	Medium
30	Implement strStr()	KMP (brute force as baseline)	O(n + m)	O(m)	Easy
31	Count and Say	Run-length encoding, iterated	O(ΣLᵢ) ≈ O(1.31ⁿ)	O(Lₙ)	Medium
32	Multiply Strings	Position-array digit math	O(m · n)	O(m + n)	Medium

The one question to ask first:

"What do I need to remember about the part of the string I have already seen?" — open brackets (stack), counts in a window (array/map), matched prefix length (KMP), or nothing beyond the current run.
If the answer fits in O(1) or O(alphabet) memory and is updated by one character at a time, the solution is linear.

What to practice next

Next page: 04 · Binary Search & Intervals — Drills 33–39, where "halve the search space" replaces "slide the window".
Previous page: 02 · Two Pointers — the read/write compaction behind Drill 29.
Theory: Sliding Window, Stack, HashMap, Two Pointers.
More problems: LeetCode sliding-window set, LeetCode stack set, and LC 3 — Template 1 with a set.

← 02 Two Pointers All drills 04 Binary Search & Intervals →