Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbacktracking

Palindrome Partitioning

Problem (restated)

Partition string s so every substring is a palindrome. Return all such partitions.

Intuition

At each start index, try every end that makes s[start..end] a palindrome, then recurse.

Approaches

Cut only on palindrome prefixes

Unverified

Time O(n * 2^n)Space O(n)

Idea. dfs(start): if start==n record path; for end≥start if palindrome, take slice, dfs(end+1), undo.

Walkthrough. “aab” → [[“a”,“a”,“b”],[“aa”,“b”]].

Trade-offs. Can precompute isPal[i][j] for O(1) checks; simple two-pointer check is fine for interview n.

Solution

export function partition(s: string): string[][] {
  const res: string[][] = [];
  const path: string[] = [];
  const isPal = (l: number, r: number): boolean => {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  };
  const dfs = (start: number) => {
    if (start === s.length) {
      res.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (!isPal(start, end)) continue;
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

export function partition(s: string): string[][] {
  const res: string[][] = [];
  const path: string[] = [];
  const isPal = (l: number, r: number): boolean => {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  };
  const dfs = (start: number) => {
    if (start === s.length) {
      res.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (!isPal(start, end)) continue;
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

Template connection

Backtracking over cut positions with a validity filter.

Reflection

Cut only when the piece you just took is a palindrome. aab yields [a, a, b] and [aa, b].
Checking the palindrome on every cut is linear in the piece. A range table stops that work from repeating.
A single letter is always a palindrome. If the whole string is one, the uncut string is an answer too.