ONE COUNTER, NO STACK
No new data structure — just the string and an index. These fifteen problems are the whole working vocabulary: single-pass parsing, two-pointer palindromes, frequency tables, word & prefix surgery, and structural checks. This deck is problems and drills only — every slide is the signal that gives a problem away, the idea, the C++ and Python, and the trap, then drills that make you recall the pattern, not just recognise it.
This is not a list of problems. It is 5 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
15 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
String problems disguise themselves badly. The phrasing names the pattern — whether order matters, whether you are walking characters or words, whether the question is about symmetry or about counts.
Roman numerals, atoi, nesting depth, stripping outer brackets.
One left-to-right pass with a running stateO(n) · O(1)Symmetry about a centre — verify one, or grow the best one.
Two pointers: inward to verify, outward to growO(n) · O(n²)The question survives shuffling the letters, so only counts matter.
Frequency array of 26 — count, don't sortO(n) · O(1)The unit of work is a word or a prefix, not a character.
Tokenise, or compare column by columnO(total length)Circular sameness — every rotation is a window of a doubled string.
Length check, then substring of s + sO(n) with a good searchA one-to-one letter mapping must hold in both directions.
Two maps, or a map plus a used-setO(n) · O(1)Almost everything here is a single O(n) pass. The bound rarely rules an approach out — what does is substr(), which copies: take one per iteration and a linear scan quietly becomes quadratic.
BOUNDED ALPHABET ⇒ 26-SLOT COUNT, NOT A HASH MAP
Five families, fifteen problems, and no lectures — this topic has no harvested series, so each family opens with its own pair of priming drills and closes with a mechanism you can step through. Go in order: the single-pass family sets up everything after it.
A C++ std::string of length n — what are the costs of s[i], s.substr(i, k), and s += c (amortised)?
Indexing is O(1), but substr copies. s.substr(i, k) allocates and copies k characters — build a loop that takes a substring each iteration and an O(n) scan quietly becomes O(n²). Appending with += is amortised O(1) because the buffer grows geometrically. In Python the trap is sharper: strings are immutable, so s += c in a loop is O(n²) — build a list and ''.join() at the end. Knowing which string op secretly copies is half of writing fast string code.
You need to count letters of a lowercase-only string. What is the right container, and why not a hash map?
A 26-slot array indexed by c - 'a'. For a bounded alphabet it is strictly better than a hash map: O(1) with tiny constants, no hashing, and — crucially — two frequency tables can be compared with a single == over 26 ints. Reserve the hash map for genuinely unbounded keys (Unicode, words, arbitrary tokens). Recognising the alphabet is bounded is the cue that turns a map into an array and an O(n log n) sort into an O(n) count.
What do all four parsing problems (remove-outermost, max-depth, Roman, atoi) have in common structurally?
A single pass with a running state. None of them needs a data structure heavier than a couple of integers: a depth counter for parentheses, an accumulator with a look-ahead rule for Roman, a sign and a clamped value for atoi. The skill is picking what to carry. Once you see the family, you stop looking for a trick and start writing the loop.
Removing the outermost parentheses of each primitive from "(()())(())" using a depth counter, what comes out?
"()()()". Walk with a depth d. On '(': if d > 0 it is an inner paren, keep it, then d++. On ')': d-- first, then if d > 0 keep it. The outermost pair of each primitive block sits exactly where d touches 0, so the test drops precisely those. No stack, one integer.
Nesting depth looks like it wants a stack, and it does not. '(' is +1 and ')' is −1, so a single running counter already holds how deep you are — and the peak it reaches is the answer. Nothing is stored, so the space is O(1) rather than O(n). Watch the counter climb to 3 and come back to 0: ending at exactly zero is also what balanced means, which is the same one-pass scan answering a second question for free. Reaching for a stack here is the reflex this slide exists to break.
Parentheses (or brackets) and a notion of nesting depth. The moment a problem is about balanced symbols and 'outermost' or 'primitive' pieces, a running depth counter — not a stack — is usually enough.
A primitive block's outermost pair is exactly where the depth touches 0. Carry a depth d: on '(' keep it only if d > 0 (it is inner), then increment; on ')' decrement first, then keep it only if d > 0. The outermost symbols are dropped automatically.
// The outermost pair of each primitive is where depth hits 0. // Carry a single depth counter; a stack is overkill here. string removeOuterParentheses(string s) { string out; int d = 0; for (char c : s) { if (c == '(') { if (d > 0) out += c; d++; } else { d--; if (d > 0) out += c; } } return out; }
// The outermost pair of each primitive is where depth hits 0. // Carry a single depth counter; a stack is overkill here. public String removeOuterParentheses(String s) { StringBuilder out = new StringBuilder(); int d = 0; for (char c : s.toCharArray()) { if (c == '(') { if (d > 0) out.append(c); d++; } else { d--; if (d > 0) out.append(c); } } return out.toString(); }
# The outermost pair of each primitive is where depth hits 0. def removeOuterParentheses(s): out, d = [], 0 for c in s: if c == '(': if d > 0: out.append(c) d += 1 else: d -= 1 if d > 0: out.append(c) return ''.join(out)
Getting the increment/decrement order wrong. For '(' you test d > 0 before incrementing; for ')' you decrement before testing. Swap either order and you keep the outermost paren or drop an inner one. Also resist reaching for a stack — the depth integer is the whole solution.
“Maximum nesting depth” of balanced parentheses, with other characters mixed in. The word depth is the tell: a counter that rises on '(' and falls on ')', tracking its peak.
Ignore everything that is not a parenthesis. Keep a running depth; the answer is the largest value it ever reaches. Because the input is guaranteed valid (VPS), the counter never goes negative and you never need to validate.
// Depth rises on '(' and falls on ')'; the answer is its peak. int maxDepth(string s) { int depth = 0, best = 0; for (char c : s) { if (c == '(') best = max(best, ++depth); else if (c == ')') depth--; } return best; }
// Depth rises on '(' and falls on ')'; the answer is its peak. public int maxDepth(String s) { int depth = 0, best = 0; for (char c : s.toCharArray()) { if (c == '(') best = Math.max(best, ++depth); else if (c == ')') depth--; } return best; }
# Depth rises on '(' and falls on ')'; the answer is its peak. def maxDepth(s): depth = best = 0 for c in s: if c == '(': depth += 1 best = max(best, depth) elif c == ')': depth -= 1 return best
Over-engineering a valid input. The string is a guaranteed valid parentheses string, so there is no need to check balance, use a stack, or handle negatives — a single counter and its running max is the entire problem. Reaching for a stack here is the mistake the previous problem warned about, again.
A Roman numeral — or any place-value system where a smaller symbol before a larger one means subtraction. The signal is a fixed symbol→value table plus a look-ahead comparison.
Walk left to right. Normally you add each symbol's value; the one exception is when a symbol is smaller than the one immediately after it (IV, IX, XL…), where it is subtracted instead. One comparison with the next character decides the sign.
// Add each value, except subtract when a symbol precedes a larger one. int romanToInt(string s) { unordered_map<char,int> v = {{'I',1},{'V',5},{'X',10},{'L',50}, {'C',100},{'D',500},{'M',1000}}; int total = 0, n = s.size(); for (int i = 0; i < n; i++) { if (i + 1 < n && v[s[i]] < v[s[i+1]]) total -= v[s[i]]; else total += v[s[i]]; } return total; }
// Add each value, except subtract when a symbol precedes a larger one. public int romanToInt(String s) { Map<Character,Integer> v = Map.of('I',1,'V',5,'X',10,'L',50, 'C',100,'D',500,'M',1000); int total = 0, n = s.length(); for (int i = 0; i < n; i++) { int cur = v.get(s.charAt(i)); if (i + 1 < n && cur < v.get(s.charAt(i + 1))) total -= cur; // IV, IX else total += cur; } return total; }
# Add each value, except subtract when a symbol precedes a larger one. def romanToInt(s): v = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000} total, n = 0, len(s) for i in range(n): if i + 1 < n and v[s[i]] < v[s[i+1]]: total -= v[s[i]] else: total += v[s[i]] return total
Special-casing the six subtractive pairs by hand. Hard-coding IV, IX, XL, XC, CD, CM is error-prone; the single rule “subtract when this value is less than the next” covers all of them. The other slip is reading s[i+1] without the i+1 < n bound at the last character.
“Parse an integer from messy text” — leading spaces, an optional sign, digits, then junk, with overflow to clamp. atoi is the canonical state-machine parse; the difficulty is entirely in the order and the clamp.
Four phases in strict order: skip leading spaces, read at most one sign, read digits until a non-digit, and stop. Build the value digit by digit but clamp to the 32-bit range before it can overflow, not after.
// Skip spaces -> one sign -> digits, clamping BEFORE each multiply. int myAtoi(string s) { int i = 0, n = s.size(), sign = 1; long x = 0; while (i < n && s[i] == ' ') i++; if (i < n && (s[i] == '+' || s[i] == '-')) sign = (s[i++] == '-') ? -1 : 1; while (i < n && isdigit(s[i])) { x = x * 10 + (s[i++] - '0'); if (sign * x > INT_MAX) return INT_MAX; // clamp before overflow if (sign * x < INT_MIN) return INT_MIN; } return (int)(sign * x); }
// Skip spaces -> one sign -> digits, clamping BEFORE each multiply. public int myAtoi(String s) { int i = 0, n = s.length(), sign = 1; long x = 0; while (i < n && s.charAt(i) == ' ') i++; if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) sign = (s.charAt(i++) == '-') ? -1 : 1; while (i < n && Character.isDigit(s.charAt(i))) { x = x * 10 + (s.charAt(i++) - '0'); if (sign == 1 && x > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (sign == -1 && -x < Integer.MIN_VALUE) return Integer.MIN_VALUE; } return (int) (sign * x); }
# Skip spaces -> one sign -> digits, clamping as you build. def myAtoi(s): i, n, sign, x = 0, len(s), 1, 0 while i < n and s[i] == ' ': i += 1 if i < n and s[i] in '+-': sign = -1 if s[i] == '-' else 1 i += 1 INT_MIN, INT_MAX = -2**31, 2**31 - 1 while i < n and s[i].isdigit(): x = x * 10 + int(s[i]); i += 1 if sign * x <= INT_MIN: return INT_MIN if sign * x >= INT_MAX: return INT_MAX return sign * x
Checking overflow after the multiply. In C++ int, x*10 + d can already have wrapped by the time you test it — carry the running value in a long (or clamp against the bound before multiplying). The second trap is phase order: a sign after a digit, or a space after a sign, must end the parse — spaces, then one sign, then digits, nothing revisited.
Valid Palindrome moves two pointers inward; Longest Palindromic Substring expands two pointers outward. What is the shared invariant?
A pair of indices bracketing a symmetric candidate. Checking a palindrome walks l up and r down comparing s[l] and s[r]; growing one starts l = r (or l, r adjacent) and pushes them apart while the ends match. Same two pointers, opposite directions — verify versus discover. Seeing them as one idea is why the second problem is not scary once the first is automatic.
This longest-palindrome expands around every index but fails on "cbbd" (returns "b" instead of "bb"). What is missing?
for (int i = 0; i < n; i++) { // odd centre only expand(i, i); // no even-centre call }
It forgets the even centres. A palindrome can be centred on a character (odd length) or on the gap between two equal characters (even length, like the bb in cbbd). So you must call both expand(i, i) and expand(i, i+1) at each index — 2n − 1 centres in all. Missing the even case is the single most common longest-palindrome bug.
The naive palindrome check builds a reversed copy and compares — O(n) extra space for a question that needs none. Symmetry is a two-pointer shape: start at both ends, compare, and step both inward. A match retires two characters at once, so the pointers meet after n/2 comparisons; a single mismatch returns false immediately, without reading the rest. O(n) time, O(1) space, no copy. The same L/R shape drives the rest of this family.
“Is it a palindrome” with the twist of ignoring case and non-alphanumeric characters. Two pointers from the ends, skipping what does not count — the archetypal inward two-pointer scan.
Put one pointer at each end. Advance each past any non-alphanumeric character, then compare the two in lowercase; if they ever differ it is not a palindrome. Meet in the middle and it is. O(1) space — no cleaned copy needed.
// Two pointers inward, skipping non-alphanumerics, comparing lowercase. bool isPalindrome(string s) { int l = 0, r = s.size() - 1; while (l < r) { while (l < r && !isalnum(s[l])) l++; while (l < r && !isalnum(s[r])) r--; if (tolower(s[l]) != tolower(s[r])) return false; l++; r--; } return true; }
// Two pointers inward, skipping non-alphanumerics, comparing lowercase. public boolean isPalindrome(String s) { int l = 0, r = s.length() - 1; while (l < r) { while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++; while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--; if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false; l++; r--; } return true; }
# Two pointers inward, skipping non-alphanumerics, comparing lowercase. def isPalindrome(s): l, r = 0, len(s) - 1 while l < r: while l < r and not s[l].isalnum(): l += 1 while l < r and not s[r].isalnum(): r -= 1 if s[l].lower() != s[r].lower(): return False l += 1; r -= 1 return True
Keeping l < r in the inner skip loops. If you skip without re-checking the bound, the pointers can cross while hunting for the next alphanumeric and you compare garbage or read out of range. Build the filter into the same loop rather than allocating a cleaned string — the two-pointer scan is O(1) space.
“Longest palindromic substring.” Substrings + palindrome + “longest” points to expand around centre: every palindrome has a centre, so try all of them and grow outward.
A palindrome is defined by its centre and mirror symmetry. There are 2n − 1 centres — each character (odd length) and each gap between adjacent characters (even length). From each, expand while the two ends match; keep the longest span seen. O(n²), O(1) space, and far simpler than DP.
// Every palindrome has a centre; try all 2n-1 and grow outward. string longestPalindrome(string s) { if (s.empty()) return ""; int bestL = 0, bestR = 0; // inclusive span auto expand = [&](int l, int r) { while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; } if (r - l - 2 > bestR - bestL) { bestL = l + 1; bestR = r - 1; } }; for (int i = 0; i < (int)s.size(); i++) { expand(i, i); // odd length expand(i, i + 1); // even length } return s.substr(bestL, bestR - bestL + 1); }
// Every palindrome has a centre; try all 2n-1 and grow outward. private int bestL = 0, bestR = 0; // inclusive span public String longestPalindrome(String s) { if (s.isEmpty()) return ""; for (int i = 0; i < s.length(); i++) { expand(s, i, i); // odd centres expand(s, i, i + 1); // EVEN centres - the classic omission } return s.substring(bestL, bestR + 1); } private void expand(String s, int l, int r) { while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; } l++; r--; // step back inside if (r - l > bestR - bestL) { bestL = l; bestR = r; } }
# Every palindrome has a centre; try all 2n-1 and grow outward. def longestPalindrome(s): best = "" def expand(l, r): while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1; r += 1 return s[l+1:r] # widest match found for i in range(len(s)): for cand in (expand(i, i), expand(i, i + 1)): if len(cand) > len(best): best = cand return best
Only expanding around single characters. That misses every even-length palindrome (abba, the bb in cbbd). You must try both (i, i) and (i, i+1) centres. Also note the post-loop span arithmetic: after the while exits, the last matching bounds are l+1 .. r-1, not l .. r.
Valid Anagram can be done by sorting both strings (O(n log n)) or by counting (O(n)). When is the counting version strictly better, and how does it end?
Count up for one, down for the other, then check all zero. A single 26-slot array: increment on s, decrement on t; if the lengths match and every slot returns to 0 they are anagrams. That is O(n) versus the sort's O(n log n), and O(1) space for a bounded alphabet. The general lesson: order doesn't matter ⇒ count, don't sort.
The 'beauty' of a substring is (max char frequency − min non-zero frequency). For "aabcb", the beauty of the whole string is:
1. In "aabcb" the counts are a:2, b:2, c:1; the most frequent letter appears 2 times, the least frequent present letter 1 time, so beauty = 2 − 1 = 1. Summing this over all substrings is O(n²·Σ): fix a start, extend the end one char at a time updating a rolling frequency table, and read max − min each step. The min must be over present letters only — zeros are not in the alphabet of the substring.
The phrase to listen for is anagram, how many times, rearrange — all of them mean the order is irrelevant, and the instinct to sort (O(n log n)) is a trap. One pass filling a 26-slot table is O(n), and afterwards every order-free question about the string is a lookup rather than another scan. The trap this animation makes concrete is the minimum: it is over letters that are present, so the twenty-odd zero slots must be skipped — count them and the answer is always wrong by exactly the minimum.
“Are these two strings anagrams” — order does not matter, only the multiset of characters. That is the cue to count, not to sort.
If the lengths differ they cannot be anagrams. Otherwise a single frequency array: increment for each character of the first string, decrement for the second. They are anagrams exactly when every count returns to zero.
// Order doesn't matter -> count, don't sort. One array, up then down. bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; int cnt[26] = {0}; for (char c : s) cnt[c - 'a']++; for (char c : t) cnt[c - 'a']--; for (int x : cnt) if (x) return false; return true; }
// Order doesn't matter -> count, don't sort. One array, up then down. public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] cnt = new int[26]; for (char c : s.toCharArray()) cnt[c - 'a']++; for (char c : t.toCharArray()) cnt[c - 'a']--; for (int x : cnt) if (x != 0) return false; return true; // O(n) and O(1) space }
# Order doesn't matter -> count, don't sort. from collections import Counter def isAnagram(s, t): return len(s) == len(t) and Counter(s) == Counter(t)
Sorting when counting is O(n). Sorting both strings works but is O(n log n); for a bounded alphabet the count-array beats it and, as a bonus, generalises to “is one an anagram of a substring of the other” (sliding window). If the alphabet is Unicode, swap the 26-array for a hash map — but keep the count-don't-sort instinct.
“Sort the characters by how often they appear” — output driven by frequency, not by the characters' natural order. Count first, then order the counts.
Tally every character's frequency, then emit characters most-frequent first, each repeated its count of times. You can sort the (char, count) pairs in O(k log k), or bucket by frequency in O(n) since no count exceeds n.
// Count, then emit most-frequent first. string frequencySort(string s) { unordered_map<char,int> f; for (char c : s) f[c]++; vector<pair<int,char>> v; for (auto& [c, n] : f) v.push_back({n, c}); sort(v.rbegin(), v.rend()); // by descending frequency string out; for (auto& [n, c] : v) out.append(n, c); return out; }
// Count, then emit most-frequent first. public String frequencySort(String s) { Map<Character,Integer> f = new HashMap<>(); for (char c : s.toCharArray()) f.merge(c, 1, Integer::sum); List<Character> keys = new ArrayList<>(f.keySet()); keys.sort((a, b) -> Integer.compare(f.get(b), f.get(a))); // descending StringBuilder out = new StringBuilder(); for (char c : keys) for (int i = 0; i < f.get(c); i++) out.append(c); return out.toString(); }
# Count, then emit most-frequent first. from collections import Counter def frequencySort(s): return ''.join(c * n for c, n in Counter(s).most_common())
Sorting the characters instead of by their counts. The order is by frequency, so a rare character must come last regardless of its letter value; sort the (count, char) pairs, not the raw string. For the O(n) version, bucket characters by their frequency (1..n) and read buckets high to low — no comparison sort at all.
“Sum a per-substring statistic over ALL substrings”, where the statistic is maxFreq − minFreq. O(n²) substrings with a rolling frequency table is the intended shape.
There are O(n²) substrings, but you do not recount each from scratch. Fix a start i; extend the end j one character at a time, updating a frequency table incrementally, and add max − min (over present characters) at every step. Σ = 26, so each update and read is O(26).
// Fix a start, extend the end, keep a rolling frequency table. int beautySum(string s) { int n = s.size(), total = 0; for (int i = 0; i < n; i++) { int f[26] = {0}; for (int j = i; j < n; j++) { f[s[j] - 'a']++; int mx = 0, mn = INT_MAX; for (int k = 0; k < 26; k++) if (f[k]) { // present chars only mx = max(mx, f[k]); mn = min(mn, f[k]); } total += mx - mn; } } return total; }
// Fix a start, extend the end, keep a rolling frequency table. public int beautySum(String s) { int n = s.length(), total = 0; for (int i = 0; i < n; i++) { int[] f = new int[26]; for (int j = i; j < n; j++) { f[s.charAt(j) - 'a']++; int mx = 0, mn = Integer.MAX_VALUE; for (int c = 0; c < 26; c++) { if (f[c] == 0) continue; // absent letters are NOT the min mx = Math.max(mx, f[c]); mn = Math.min(mn, f[c]); } total += mx - mn; } } return total; }
# Fix a start, extend the end, keep a rolling frequency table. def beautySum(s): n, total = len(s), 0 for i in range(n): f = [0] * 26 for j in range(i, n): f[ord(s[j]) - 97] += 1 present = [x for x in f if x] total += max(present) - min(present) return total
Taking the minimum over all 26 slots including the zeros. The minimum must be over characters actually present in the substring — a zero is not a frequency in that substring, and including it makes every beauty max − 0. The other trap is recounting each substring from scratch (O(n³)); extend the previous count by one character instead.
“Reverse the word order of a sentence” versus “reverse each word in place” — what is the operational difference?
One reorders the words; the other reorders letters within each word. Reverse Words in a String splits on whitespace, drops the empties, reverses the list and rejoins with single spaces. Reverse Words III leaves the word order alone and reverses the characters inside each maximal non-space span. A neat one-liner for both: reverse the whole string, then reverse each word — do it once and you get order-reversal, apply the inner reversal only and you get III.
Largest Odd Number in String scans "52427" for the answer. What is it, and what is the rule?
"52427". Any prefix ending in an odd digit is an odd number, and the longest such prefix is the largest — so scan from the right for the first odd digit and return everything up to it. Here the final 7 is odd, so the whole string qualifies. If it were "5240" you would back up to the 5 and return "5"; all-even gives "". Greedy from the correct end, O(n).
The common prefix is not found by comparing strings to each other in pairs — it is found by walking one index at a time across all of them. Take column 0 of every word, then column 1, and stop at the first disagreement; everything before that column is the answer. Because the very first mismatch ends it, the work is bounded by the shortest word and not the longest, and running off the end of a short string counts as a disagreement too. Here flower / flow / flight agree on f and l, then split at column 2 — so the answer is "fl", decided after three columns rather than eighteen characters.
“Reverse the ORDER of the words” and normalise spacing (leading, trailing, and multiple inner spaces collapse to one). A tokenise-and-reverse on the list of words.
Split the sentence on whitespace, discarding the empty tokens that leading/trailing/double spaces produce, reverse the resulting list of words, and rejoin with single spaces. The O(1)-space version reverses the whole string then reverses each word back.
// Tokenise on whitespace, drop blanks, reverse the word list, rejoin. string reverseWords(string s) { vector<string> w; stringstream ss(s); string tok; while (ss >> tok) w.push_back(tok); // >> skips runs of spaces reverse(w.begin(), w.end()); string out; for (int i = 0; i < (int)w.size(); i++) out += (i ? " " : "") + w[i]; return out; }
// Tokenise on whitespace, drop blanks, reverse the word list, rejoin. public String reverseWords(String s) { String[] w = s.trim().split(" +"); // " +" needs no escaping Collections.reverse(Arrays.asList(w)); return String.join(" ", w); // single spaces on the way out }
# str.split() with no arg splits on runs of whitespace and drops blanks. def reverseWords(s): return ' '.join(reversed(s.split()))
Splitting on a single space and forgetting the empties. Leading, trailing and doubled spaces create empty tokens; a naive split(' ') keeps them and you emit stray spaces. Split on runs of whitespace (C++ >>, Python split() with no argument) so the blanks vanish, then join with exactly one space.
“Reverse the letters of each word but KEEP the word order” and keep the spaces where they are. Reverse each maximal non-space span in place — the mirror image of the previous problem.
Word order and spacing stay exactly as given; only the characters inside each word flip. Walk the string, and each time you hit a maximal run of non-space characters, reverse that span with two pointers. Spaces are left untouched.
// Reverse each maximal non-space span in place; spaces stay put. string reverseWords(string s) { int n = s.size(), i = 0; while (i < n) { if (s[i] == ' ') { i++; continue; } int j = i; while (j < n && s[j] != ' ') j++; // word is [i, j) reverse(s.begin() + i, s.begin() + j); i = j; } return s; }
// Reverse each maximal non-space span in place; spaces stay put. public String reverseWords(String s) { char[] a = s.toCharArray(); int n = a.length, i = 0; while (i < n) { if (a[i] == ' ') { i++; continue; } int j = i; while (j < n && a[j] != ' ') j++; // word is [i, j) for (int l = i, r = j - 1; l < r; l++, r--) { char t = a[l]; a[l] = a[r]; a[r] = t; } i = j; } return new String(a); // word ORDER is untouched }
# Reverse each word's letters, keep word order and spacing. def reverseWords(s): return ' '.join(w[::-1] for w in s.split(' '))
Confusing this with word-order reversal. Here the words stay in place and the letters flip; there the words move and the letters do not. If the problem guarantees single spaces, a plain split(' ') is correct — but do not collapse spaces, because unlike problem 10 the spacing is meant to be preserved.
“Longest common prefix of an array of strings.” A prefix is shared only if every string agrees at that position, so scan column by column and stop at the first disagreement.
Look at character position 0 across all strings, then position 1, and so on. The moment one string is too short or differs from the first string's character at that column, the common prefix ends. Return everything before that column.
// Scan column by column; stop at the first string that disagrees. string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; for (int j = 0; j < (int)strs[0].size(); j++) { char c = strs[0][j]; for (int i = 1; i < (int)strs.size(); i++) if (j >= (int)strs[i].size() || strs[i][j] != c) return strs[0].substr(0, j); } return strs[0]; }
// Scan column by column; stop at the first string that disagrees. public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; for (int j = 0; j < strs[0].length(); j++) { char c = strs[0].charAt(j); for (int i = 1; i < strs.length; i++) if (j == strs[i].length() || strs[i].charAt(j) != c) return strs[0].substring(0, j); // first disagreement } return strs[0]; }
# Scan column by column; stop at the first string that disagrees. def longestCommonPrefix(strs): if not strs: return "" for j, c in enumerate(strs[0]): for other in strs[1:]: if j >= len(other) or other[j] != c: return strs[0][:j] return strs[0]
Forgetting the length guard when a string is shorter than the prefix. Reading strs[i][j] without checking j < len(strs[i]) reads out of bounds on the shortest string, which is exactly where the prefix must end. Handle the empty array too — the answer there is the empty string, not a crash.
“Largest odd number that is a substring” of a digit string — and the answer must be a prefix, because dropping trailing digits keeps the start. That makes it a greedy scan from the right for the last odd digit.
A number is odd iff its last digit is odd. Any prefix ending at an odd digit is an odd number, and the longest such prefix is the largest. So scan from the right for the first odd digit; the answer is the whole prefix up to and including it. All-even means no odd number exists.
// Odd <-> last digit is odd. The largest odd substring is the longest // prefix ending in an odd digit -> scan from the right. string largestOddNumber(string num) { for (int i = num.size() - 1; i >= 0; i--) if ((num[i] - '0') % 2 == 1) return num.substr(0, i + 1); return ""; }
// Odd <-> last digit is odd. The largest odd substring is the longest // prefix ending in an odd digit -> scan from the right. public String largestOddNumber(String num) { for (int i = num.length() - 1; i >= 0; i--) if ((num.charAt(i) - '0') % 2 == 1) return num.substring(0, i + 1); return ""; // every digit even }
# Odd <-> last digit is odd; take the longest prefix ending odd. def largestOddNumber(num): for i in range(len(num) - 1, -1, -1): if int(num[i]) % 2 == 1: return num[:i + 1] return ''
Scanning from the left or trimming leading zeros. The greedy direction is from the right: you want the longest prefix, so you keep as many leading digits as possible and only chop the even tail. Do not strip leading zeros — the problem treats the substring as-is — and return "" (not "0") when every digit is even.
Why does an isomorphic-strings check need TWO maps (or a map plus a used-set) rather than one?
Isomorphism is a bijection, and one map only guards one side. A single s → t map ensures each source character is consistent, but it would happily accept “ba” → “aa”, mapping both b and a onto a. Enforcing the reverse map t → s too (or a set of already-used targets) forbids that collision. Any “consistent renaming” problem needs both directions.
Rotate String asks if goal is a rotation of s. What is the one-line reduction?
|s| == |goal| and goal ⊂ s + s. Concatenating s with itself lays out every rotation of s as a length-|s| window, so a single substring search settles it — after the length guard, which stops a shorter goal from matching by accident. It is the same doubling trick that turns many circular-array problems into linear ones.
This is the sharpest trick in the deck. Instead of generating each rotation and comparing — a loop with an off-by-one waiting in it — double the string. Every rotation of s appears in s + s as one contiguous window of length n, so “is goal a rotation of s?” collapses into a single substring search. Watch the answer land at offset 2, straddling the seam between the two copies — that is precisely the rotation a naive loop is most likely to fumble. Guard the equal-length check first, or "ab" matches inside "abab" for the wrong reason.
“Isomorphic” / “consistent one-to-one replacement” of characters. The word bijection is the tell: you need a mapping that is consistent in both directions.
Walk both strings in lockstep. Maintain a map s → t and a map t → s. At each position, if either map already binds the character to a different partner, it is not isomorphic. If both agree (or are unset, in which case you set them), continue.
// A bijection needs BOTH directions consistent: s->t and t->s. bool isIsomorphic(string s, string t) { if (s.size() != t.size()) return false; int st[128], ts[128]; memset(st, -1, sizeof st); memset(ts, -1, sizeof ts); for (int i = 0; i < (int)s.size(); i++) { unsigned char a = s[i], b = t[i]; if (st[a] == -1 && ts[b] == -1) { st[a] = b; ts[b] = a; } else if (st[a] != b || ts[b] != a) return false; } return true; }
// A bijection needs BOTH directions consistent: s->t and t->s. public boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) return false; int[] st = new int[128], ts = new int[128]; Arrays.fill(st, -1); Arrays.fill(ts, -1); for (int i = 0; i < s.length(); i++) { char a = s.charAt(i), b = t.charAt(i); if (st[a] == -1 && ts[b] == -1) { st[a] = b; ts[b] = a; } else if (st[a] != b || ts[b] != a) return false; // BOTH must agree } return true; }
# A bijection needs BOTH directions consistent: s->t and t->s. def isIsomorphic(s, t): if len(s) != len(t): return False st, ts = {}, {} for a, b in zip(s, t): if (a in st and st[a] != b) or (b in ts and ts[b] != a): return False st[a], ts[b] = b, a return True
Mapping only one direction. A single s → t map accepts “badc” → “baba”, letting two different source characters collapse onto the same target. Enforce the reverse map too (or a used-target set). It is the exact bug the group drill flagged — isomorphism is a bijection, and a bijection is two-way.
“Is goal a ROTATION of s”. Rotation of a string is the doubling trick: every rotation of s is a window of s + s, so it reduces to a substring search.
If the lengths differ, no rotation is possible. Otherwise concatenate s with itself: it contains every rotation of s as a contiguous block of length |s|. So goal is a rotation iff it appears as a substring of s + s.
// Every rotation of s is a window of s+s -> one substring search. bool rotateString(string s, string goal) { return s.size() == goal.size() && (s + s).find(goal) != string::npos; }
// Every rotation of s is a window of s+s -> one substring search. public boolean rotateString(String s, String goal) { return s.length() == goal.length() && (s + s).contains(goal); }
# Every rotation of s is a window of s+s -> one substring search. def rotateString(s, goal): return len(s) == len(goal) and goal in (s + s)
Skipping the length guard. Without |s| == |goal|, a goal that is a genuine but shorter substring of s + s passes as a rotation when it is not. Check equal lengths first, then the substring — the guard is what makes the doubling trick exact.
Three different statements: “is b a rotation of a”, “does a contain b”, and “are the two strings anagrams”. Which pair shares a core trick?
Rotation is a substring search in disguise. Every rotation of a appears as a contiguous window of a + a, so “is b a rotation of a” becomes “is b a substring of a+a” (after the length check) — the same primitive as “does a contain b”. Anagram is the odd one out: it throws away order entirely and only counts letters. Sorting the statement into “does order matter?” picks the tool before you write a line.
Across these fifteen, which single idea recurs most — and names its own family?
The single left-to-right pass with a running state. Remove Outermost Parentheses carries a depth; Max Nesting Depth carries a depth and its max; Roman to Integer carries an accumulator with a look-ahead rule; atoi carries a sign and a clamped value; anagram and beauty carry a frequency table. Most string problems are not about a clever data structure — they are about choosing the right thing to carry through one pass. Naming that as a family is what lets you start writing immediately instead of hunting for a trick.
String bugs are quiet: an off-by-one in a skip loop, an overflow after the multiply, a one-way map. Every one of these compiles and returns a believable answer.
s = s + c (Python) or s.substr each iteration turns an O(n) scan into O(n²). Build a vector<char> / list and join once, and take substrings by index range, not by copying.
A 26-slot array crashes or misses on uppercase, digits, spaces or Unicode. Valid Palindrome and atoi are explicitly mixed-case with punctuation — size the table 128, or filter first, and read the constraints for the real alphabet.
The classic bug is checking overflow after multiplying — it has already wrapped. Clamp before each x = x*10 + d, and respect the exact order: skip spaces → one optional sign → digits → stop at the first non-digit.
Expanding only around single characters misses even-length palindromes like abba. There are 2n − 1 centres — every index AND every gap between adjacent indices.
A map from s to t alone accepts “badc” → “baba” wrongly. The bijection must hold BOTH ways — two maps, or a map plus a used-set — or two different source chars collapse onto one target.
b can only be a rotation of a if |a| == |b|; without that guard, b being a shorter substring of a+a passes falsely. Cheap check first, then the substring search.
Fourteen recognitions, one page. The right-hand column is the tell — the phrase in the statement that should trigger the pattern before you write a line.
None of these needed a new data structure — just the right thing carried through one pass, or two pointers, or a count. Once the pattern behind each statement is automatic, the string round of an interview stops being about strings and starts being about reading the signal.
Problem links are LeetCode. No lecture playlist was supplied for this topic, so there are no concept videos — the intros, drills and the five mechanism visualisers carry it instead.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.