Strings and parsing

Specification-heavy problems where the score lives in the edge cases.

Trigger in the prompt: 'Palindrome', 'anagram', 'parse', 'format', 'compress'.

easyFirst Occurrence in a String

Find the first index where one string occurs inside another.

Trigger

Substring search — the classic string-matching question.

Approach
  1. The naive version is O(n·m): try every start position.
  2. Name KMP and what it buys: the failure function lets you avoid re-comparing a matched prefix, giving O(n + m).
  3. Say honestly whether you would write KMP from memory. Naming it and explaining the idea usually suffices.
Target complexity

O(n·m) naive, O(n + m) with KMP.

Pitfall

Claiming KMP and then failing to build the failure function. Better to write the naive version and explain KMP than to half-write it.

Say it out loud

“The naive version is n times m. KMP gets it to linear by precomputing, for each prefix, the longest proper prefix that's also a suffix — so after a mismatch it never re-compares what it already matched. I'd write the naive version here and explain KMP, unless you'd like to see it.”

Solve on LeetCode
easyLongest Common Prefix

Find the longest prefix shared by every string in a list.

Trigger

'Common prefix' across many strings.

Approach
  1. Vertical scan: compare character i across all strings, stop at the first mismatch or short string.
  2. Early exits: an empty list, or any empty string, gives an empty prefix.
  3. Mention a trie as the answer when you have many prefix queries against a fixed set.
Target complexity

O(total characters) in the worst case, O(1) extra space.

Pitfall

Not guarding against a string shorter than the current index.

Say it out loud

“A vertical scan — compare position zero across all strings, then position one, and stop at the first mismatch. If this were a repeated query against a fixed dictionary I'd build a trie instead, but for one pass this is optimal.”

Solve on LeetCode
mediumLongest Palindromic Substring

Find the longest palindromic substring.

Trigger

'Longest palindrome' inside a string.

Approach
  1. Expand around centre: 2n−1 centres, counting the gaps between characters for even lengths.
  2. Each expansion is O(n), so the whole thing is O(n²) with O(1) space.
  3. Mention Manacher's algorithm as the O(n) solution, and be honest that you would not write it under time pressure.
Target complexity

O(n²) time, O(1) space.

Pitfall

Only trying character centres and missing every even-length palindrome.

Say it out loud

“I'll expand around centres — and there are 2n minus 1 of them, because even-length palindromes are centred between characters. That's quadratic with constant space. Manacher's gets it to linear, but I wouldn't write it from memory in 45 minutes and I'd say so.”

Solve on LeetCode
mediumString Compression

Compress a character array in place using run-length encoding.

Trigger

'In place', 'modify the input array', run-length encoding.

Approach
  1. Two indices: one reading, one writing. The write index never overtakes the read index.
  2. Count each run, then write the character followed by the count's digits — only if the count exceeds one.
  3. The count is written digit by digit, since it may exceed 9.
Target complexity

O(n) time, O(1) extra space.

Pitfall

Writing the count as a single character. A run of length 12 needs two positions.

Say it out loud

“Two indices, one reading and one writing, and the writer never passes the reader — which is why in-place is safe. The detail is writing multi-digit counts one character at a time; a run of twelve isn't a single symbol.”

Solve on LeetCode
mediumString to Integer (atoi)

Parse a leading integer out of a string following a precise set of rules.

Trigger

A specification-heavy parsing problem — an edge case test in disguise.

Approach
  1. Enumerate the phases out loud: whitespace, optional sign, digits, stop at anything else.
  2. Clamp to the 32-bit range — that is the actual point of the exercise.
  3. In Python, integers do not overflow, so the clamp must be explicit.
  4. List the edge cases before coding: empty, only spaces, only a sign, leading zeros, overflow.
Target complexity

O(n) time, O(1) space.

Pitfall

Treating this as an algorithm problem. It is a careful-reading problem, and the score is in the edge cases.

Say it out loud

“There's no algorithmic difficulty here — it's a specification, so I'll enumerate the phases and the edge cases before I write anything. The one that actually matters is clamping to the 32-bit range, which in Python has to be explicit because integers don't overflow.”

Solve on LeetCode
hardText Justification

Format words into fully justified lines of a fixed width.

Trigger

A long specification with formatting rules — pure careful simulation.

Approach
  1. Greedily fill each line: add words while they fit with single spaces between them.
  2. Distribute the extra spaces left to right, so the left gaps get the remainder.
  3. The last line, and any line with one word, is left-justified with trailing padding — that is the special case everyone forgets.
  4. Say the structure before coding: one function to build a line, one loop to group words.
Target complexity

O(total characters) time, O(width) space per line.

Pitfall

Applying the justification rule to the last line. It is left-aligned, always.

Say it out loud

“This is careful simulation rather than an algorithm, so I'll structure it as two pieces: a loop that groups words greedily, and a function that formats one group. The rule I'll be explicit about is the last line, which is left-aligned rather than justified.”

Solve on LeetCode