Strings

MNEMONIC Grow while the mirror holds.

PATTERN Strings as character arrays

A string is a sequence of characters — treat it like an array and every array technique becomes available. The most-used primitives are:

• Frequency signature. A length-26 array (or a Map) counting each character. Two strings with identical signatures are anagrams. Increment for one string, decrement for the other — if everything zeros out, they match.
• Two pointers (palindrome). lo starts left, hi starts right — converge while skipping non-alphanumerics and comparing case-folded chars.
• Expand around center. Every palindrome has a center (one char for odd length, the gap between two chars for even). Expand outward as long as characters match. Covers both the longest-substring and count-all-palindromes problems in O(n²) time and O(1) space.
• Stack for bracket matching. Push opening brackets; on a closing bracket check whether the stack top is the matching opener and pop it. An empty stack at the end means valid.
• Length-prefix encoding. To serialize a list of arbitrary strings (which may contain any delimiter), prepend each string with its length and a separator: 5#hello3#foo. The decoder reads the number, then extracts exactly that many characters — no ambiguity.

KEY IDEA Grouping by signature

For the typical interview input the difference is negligible, but the count approach is asymptotically better and also handles Unicode naturally if you use a full Map instead of a 26-slot array.

COST Palindrome: naive vs expand-around-center

The brute-force approach checks every substring for palindromicity: pick every (i, j) pair and verify. That's O(n²) substrings × O(n) verification each.

There is an O(n)algorithm (Manacher's), but it is almost never required in interviews — expand-around-center is the expected answer at every major company.

REDUCTION When "string" is really another pattern

A large fraction of string problems are not fundamentally about strings — they reduce to a pattern you already know:

• Longest substring with at most k distinct chars / no repeats → sliding window with a frequency map.
• Longest common subsequence / edit distance → 2-D dynamic programming on the two-string grid.
• Prefix search / autocomplete → trie.
• Pattern matching (find all occurrences) → KMP or Rabin-Karp (rarely needed in interviews, but know the idea).

Identifying the reduction early is what separates a clean solution from a tangled one.

RUN IT Grow while the mirror holds

TRIGGERS When you see ___ → reach for ___

Reach for the string toolkit when the problem is about character identity, order, or symmetrywithin one or two words — not about subarray sums or prefix counts. The first question to ask is: "which tool fits the structure?"

RED FLAGSWhen it's NOT this pattern

• Contiguous substring + sum/condition → that's a sliding window, not a static frequency count. The window expands and contracts; a plain character map won't tell you when to shrink.
• Two-string alignment / edit cost → reach for 2-D DP. Problems like longest common subsequence or edit distance build a grid over the two strings; no pointer trick handles the full state space.
• Prefix / autocomplete / word search → a trie(prefix tree) encodes all words in shared prefixes and supports O(k) lookup. A hash map can't answer "all words with prefix X" efficiently.
• Substring "contains all characters of t" → minimum window substring is a sliding window + frequency map hybrid. The window guarantees contiguity; the map tracks the coverage deficit.

TEMPLATE Frequency-count comparison (anagram)

When → Two strings of the same length: check whether they use identical characters. Tally one string up, drain the other down, verify all zeros.

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const count = new Array(26).fill(0);          // index by charCode - 97
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;              // tally up for s
    count[t.charCodeAt(i) - 97]--;              // drain down for t
  }
  return count.every(c => c === 0);             // all balanced → anagram
}

TEMPLATE Two-pointer palindrome check

When → Determine whether a string reads the same forwards and backwards, optionally ignoring non-alphanumeric characters and case (LC 125 style).

function isPalindrome(s: string): boolean {
  let lo = 0, hi = s.length - 1;
  while (lo < hi) {
    while (lo < hi && !isAlphanumeric(s[lo])) lo++;   // skip junk left
    while (lo < hi && !isAlphanumeric(s[hi])) hi--;   // skip junk right
    if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
    lo++; hi--;
  }
  return true;
}

function isAlphanumeric(c: string): boolean {
  return /[a-zA-Z0-9]/.test(c);
}

TEMPLATE Expand around center

When → Find the longest palindromic substring or count all palindromic substrings. Expanding from every one of the 2n − 1 centers covers both odd and even lengths.

// Returns [start, end] of the longest palindromic substring
function longestPalindrome(s: string): string {
  let best = [0, 0];

  function expand(l: number, r: number): void {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      if (r - l > best[1] - best[0]) best = [l, r];
      l--; r++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd-length center
    expand(i, i + 1); // even-length center (gap between i and i+1)
  }
  return s.slice(best[0], best[1] + 1);
}

// Count all palindromic substrings (LC 647)
function countSubstrings(s: string): number {
  let count = 0;
  function expand(l: number, r: number): void {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      count++;
      l--; r++;
    }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i);
    expand(i, i + 1);
  }
  return count;
}

TEMPLATE Length-prefix encode / decode

When → Serialize a list of strings into a single string that can be unambiguously decoded even when the strings contain any character (including the delimiter).

// Length-prefix encoding: "<len>#<str><len>#<str>..."
function encode(strs: string[]): string {
  return strs.map(s => `${s.length}#${s}`).join('');
}

function decode(s: string): string[] {
  const result: string[] = [];
  let i = 0;
  while (i < s.length) {
    const hash = s.indexOf('#', i);          // find the delimiter
    const len = parseInt(s.slice(i, hash));  // read the length prefix
    result.push(s.slice(hash + 1, hash + 1 + len));
    i = hash + 1 + len;                      // jump past the payload
  }
  return result;
}

PITFALL 26-array breaks on Unicode / uppercase input

charCode - 97 assumes lowercase ASCII letters a–z. Uppercase letters, digits, or any non-ASCII character produce negative indices or out-of-range slots. Normalize with .toLowerCase() first, or switch to a Map<string, number> which works for any character set.

PITFALL Missing the even-length palindrome center

A single expand call expand(i, i) only finds palindromes of odd length. Every even-length palindrome (e.g. "abba") has its center in the gap between two adjacent characters. You must also call expand(i, i + 1) for every index, or you will silently miss all even-length palindromes.

PITFALL String concatenation in a loop

In JavaScript/TypeScript, result += charinside a loop creates a new string object on every iteration — that's O(n²) total copying. Always collect characters into an array and call .join('') once at the end for O(n) construction.

PITFALL Forgetting case and whitespace normalization

LC 125 (Valid Palindrome) explicitly strips non-alphanumerics and ignores case. Forgetting either step produces wrong answers on inputs like "A man, a plan, a canal: Panama". Apply .toLowerCase() during comparison (not once upfront, to avoid allocating a whole new string) and skip non-alphanumeric characters with an inner while loop inside the two-pointer template.

PROBLEMS