Strings

Strings are arrays of characters — with a twist

Most string problems are array problems over a small alphabet, so frequency counting and two pointers dominate. The twist: in many languages (Python, Java) strings are immutable — every “edit” makes a new string — which changes how you build results and manipulate in place.

Immutability and efficient building

Because strings are immutable, result += piece inside a loop is O(n²) (each += copies the whole prefix). Collect parts and join once:

parts = []
for token in tokens:
    parts.append(transform(token))
result = "".join(parts)             # O(n) total

(Java: StringBuilder.) For in-place character work, convert to a list/char array, mutate, then join.

Pattern 1 — Frequency counting

A fixed int[26] (lowercase) or a Counter answers anagram, permutation, and “can we form…” questions in O(n):

from collections import Counter
def is_anagram(s, t):
    return Counter(s) == Counter(t)

Group anagrams by keying a hash map on the sorted string or a count tuple. Frequency maps also drive the sliding-window string problems below.

Pattern 2 — Two pointers

Converging pointers solve palindromes and reversals in O(n)/O(1):

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]: return False
        i += 1; j -= 1
    return True

Reversing in place, comparing ends, and “reverse the words in a sentence” all use a write pointer or two converging pointers. (See the two-pointers primer.)

Pattern 3 — Sliding window

For “longest/shortest substring with property X” (longest without repeats, minimum window covering a set), grow a window with the right pointer and shrink with the left, keeping a running frequency map of the window. O(n). This is common enough to have its own primer — reach for it on any substring-with-constraint question.

Pattern 4 — Stack for nested/parsed structure

Matching/parsing problems (valid parentheses, decode string 3[ab], basic calculators) use a stack to track nesting. (See the stacks primer.)

Palindrome techniques (know all three)

Palindrome substring problems have a ladder of approaches:

• Expand around center — for each of the 2n−1 centers (each char and each gap), expand outward while characters match. O(n²) time, O(1) space — the standard answer for “longest palindromic substring” and “count palindromic substrings.”

  def expand(s, l, r):
      while l >= 0 and r < len(s) and s[l] == s[r]:
          l -= 1; r += 1
      return r - l - 1            # length of the palindrome

• DP — dp[i][j] = s[i]==s[j] and dp[i+1][j-1]; O(n²) time and space. Useful when you need all substring answers.

• Manacher’s algorithm — longest palindromic substring in O(n) by reusing mirror information. Rarely required, but name it as the optimal.

Substring search (pattern in text)

Finding a pattern p inside text t naively is O(n·m). The efficient algorithms (their own primer):

• KMP — precompute a failure/prefix function so you never re-compare; O(n + m).
• Rabin–Karp (rolling hash) — hash the pattern and each window, compare hashes; great for multiple-pattern or 2D search.
• Z-algorithm — O(n) prefix-match lengths.

Reach for these when the problem is literally “does/where does pattern occur.”

Subsequence and edit problems → DP

“Longest common subsequence,” “edit distance,” “is s a subsequence of t” (the last is a simple two-pointer; the rest are DP). When a string problem asks for an optimal transformation or alignment between two strings, it’s a 2-D DP — see the DP primers.

Useful building blocks

• Character ↔ index: ord(c) - ord('a') maps lowercase to 0..25 for array counting.
• Tries for prefix-keyed problems (autocomplete, word search) — see the tries primer.
• Rolling hash for fast substring equality/dedup.

Common pitfalls

• Quadratic concatenation — build with a list + join.
• Unicode vs ASCII — int[26] assumes lowercase ASCII; real text may need a Counter.
• Case / whitespace / punctuation — clarify whether to normalize (s.lower(), filter).
• Off-by-one in two-pointer expansion — return r - l - 1 after the loop overshoots.

Choosing in an interview

• Counting / anagram / grouping → frequency map.
• Palindrome / reverse / compare-ends → two pointers (or expand-around-center).
• Longest/shortest substring with a constraint → sliding window.
• Parsing nested structure → stack.
• Find a pattern inside text → KMP / rolling hash.
• Align/transform two strings → DP.

Name the immutability cost when you build strings, and state the O(n²)-vs-O(n) palindrome ladder — those specifics read as experience.