Festival Train Split

MediumbacktrackingAlso known as Palindrome Partitioning

A heritage railway paints each carriage a single colour and writes a train as one letter per carriage: rbrr is red, blue, red, red. For its summer festival the railway splits one long train into shorter trains, keeping the carriages in their order.

The station manager has one rule: every short train must look the same whichever way it pulls into the platform, so its colours must read the same from either end. A single carriage always qualifies. The manager wants to see every possible way to split the train.

Your task

Write trainSplits(carriages). Return every way to cut the string carriages into consecutive pieces so that each piece reads the same forwards and backwards. Write each way as the list of pieces from left to right; joined together, they must give back carriages.

The ways can be in any order, each listed once. An empty string has exactly one way, with no pieces: return [[]].

trainSplits(carriages: string) → string[][] Any order of the returned list is accepted.

Examples

Example 1

Input

carriages = "rbrr"

Output

[["r", "b", "r", "r"], ["r", "b", "rr"], ["rbr", "r"]]

Why

Single carriages always work. rr at the end reads the same both ways, and so does rbr at the start. rb, br, brr and the whole rbrr do not, so no plan can use them.

Example 2

Input

carriages = "gbbg"

Output

[["g", "b", "b", "g"], ["g", "bb", "g"], ["gbbg"]]

Why

The whole train gbbg is symmetric, so keeping it in one piece is a valid plan. bb in the middle is too. gb and gbb are not.

Constraints

0 ≤ carriages.length ≤ 12
carriages contains only lowercase letters.
Ways may be returned in any order; the pieces inside a way stay in train order.

Start with brute force

Between each pair of neighbouring carriages you either cut or you do not, so there are 2^{n − 1} cut patterns. Try them all and keep the ones where every piece is symmetric. For 12 carriages that is 2,048 patterns, which is fine, but each extra carriage doubles it: 30 carriages would mean over 500 million.

For a train like rgbyw with all colours different, only one pattern works, yet the brute force still builds all 16. Checking the first piece before going further cuts away every pattern that starts with a bad piece in one go.

Hints

0 of 4 shown

Hint 1
Look at rbrr. The first short train must start at the first carriage. Which of r, rb, rbr, rbrr read the same from both ends?
Hint 2
Once you choose a symmetric first train, the carriages that are left form the same puzzle, only shorter. Every plan is "a symmetric first train" followed by "a plan for the rest".
Hint 3
Write cut(start): for every end position from start onward, if the piece from start to end is symmetric, add it to the current plan and call cut(end + 1). When start reaches the end of the string, the current plan is complete.
Hint 4
Check a piece with two pointers that walk in from both ends. Push the piece before the recursive call and pop it after, and record a copy of the plan when it is complete. A piece that is not symmetric is skipped, along with every plan that would start with it.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Choose the first train, then solve the rest the same way. Only symmetric first trains are worth following, so a bad piece is rejected before anything is built on top of it.

Trace rbrr:

First train r (symmetric). Rest brr: b works, then the rest rr gives [r, r] or [rr]. Record [r, b, r, r] and [r, b, rr]. br and brr are not symmetric.
First train rb: not symmetric. Skip it and everything that would follow it.
First train rbr: symmetric. Rest r: record [rbr, r].
First train rbrr: not symmetric. Done.

Three plans. A common mistake is a greedy rule such as "always take the longest symmetric piece": it finds one plan, not all of them, and the task asks for every one.

Reference solution

function trainSplits(carriages) {
  const plans = [];
  const pieces = [];
  function symmetric(lo, hi) { // carriages[lo..hi] reads the same both ways?
    while (lo < hi) {
      if (carriages[lo] !== carriages[hi]) return false;
      lo++;
      hi--;
    }
    return true;
  }
  function cut(start) {
    if (start === carriages.length) {
      plans.push([...pieces]); // every carriage is placed
      return;
    }
    for (let end = start; end < carriages.length; end++) {
      if (!symmetric(start, end)) continue; // only symmetric trains
      pieces.push(carriages.slice(start, end + 1));
      cut(end + 1);
      pieces.pop();
    }
  }
  cut(0);
  return plans;
}

def train_splits(carriages):
    plans = []
    pieces = []
 
    def symmetric(lo, hi):  # carriages[lo..hi] reads the same both ways?
        while lo < hi:
            if carriages[lo] != carriages[hi]:
                return False
            lo += 1
            hi -= 1
        return True
 
    def cut(start):
        if start == len(carriages):
            plans.append(pieces[:])     # every carriage is placed
            return
        for end in range(start, len(carriages)):
            if symmetric(start, end):   # only symmetric trains are allowed
                pieces.append(carriages[start:end + 1])
                cut(end + 1)
                pieces.pop()
 
    cut(0)
    return plans

TimeO(n · 2ⁿ)In the worst case (all one colour) there are 2ⁿ⁻¹ plans, and building and copying each costs O(n). Symmetry checks add at most O(n) per piece tried.

SpaceO(n)The recursion depth and the current plan are at most n pieces, not counting the output.

Learn the idea: Backtracking Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code