Marauder Bot

Problem

Given a string, split it into a sequence of substrings such that every substring reads the same forwards and backwards. Return every such way of partitioning the string.

Example. For "aab", the valid partitions are ["a", "a", "b"] and ["aa", "b"].

Key idea

A partition is a sequence of cut points, so this is backtracking over where to place the next cut. At each position, try every end point for the next piece, check whether it is a palindrome, and if so recurse on the remainder with the piece appended to the partial partition; otherwise that cut is invalid and gets skipped.

Keep a cursor for how much of the string has been consumed. From the cursor, try every end point through the end of the string, testing each candidate for the palindrome property. Recurse into the remaining suffix whenever a candidate passes, and record the accumulated partition once the cursor reaches the string's end, since that means every piece so far was validated. Checking a substring from scratch on every visit is correct but repeats work across branches; precomputing which ranges are palindromic ahead of time, with a small dynamic-programming table, avoids re-scanning the same range more than once.

Solution

function partition(s: string): string[][] {
  const result: string[][] = [];
  const partial: string[] = [];

  function isPalindrome(start: number, end: number): boolean {
    let left = start;
    let right = end;
    while (left < right) {
      if (s[left] !== s[right]) {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }

  function backtrack(cursor: number): void {
    if (cursor === s.length) {
      // Reached the end with every piece validated; record this partition.
      result.push([...partial]);
      return;
    }

    for (let end = cursor; end < s.length; end++) {
      // Only extend the partition with a piece that is itself a palindrome.
      if (isPalindrome(cursor, end)) {
        partial.push(s.slice(cursor, end + 1));
        backtrack(end + 1);
        partial.pop();
      }
    }
  }

  backtrack(0);
  return result;
}

Complexity

Time: O(n · 2ⁿ). Up to 2ⁿ ways to partition a string of length n, each costing O(n) to validate and copy without a precomputed table; building that table costs an additional O(n²).
Space: O(n). Recursion depth, plus O(n²) if using the precomputed table.

Watch out for

A single character, and the split reached at the string's end, are always trivially valid palindromic pieces; don't special-case them away.
Skipping the precomputation is still correct, but re-testing the same substring across branches can dominate runtime even though the enumeration bound is unchanged.

Pattern

This is substring backtracking with a validity filter: the same "try every cut, recurse on the remainder" shape used in Word Break, but generating every valid partition instead of testing whether one exists.

Palindrome Partitioning