Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Recursion & Backtracking

Palindrome Partitioning

Medium · Recursion & Backtracking · Asked at Amazon, Google, Microsoft, Bloomberg

Split the string into pieces so that every piece is a palindrome. Print the number of ways, then every partition on its own line (pieces separated by spaces). List the partitions in the order a backtracking search produces them when it always tries the shorter first piece first.

Input

A single lowercase string s.

Output

The count, then the partitions.

Constraints

For each prefix that is a palindrome, take it as the first piece and recurse on the rest.

Example 1

Input

aab

Output

2
a a b
aa b

Example 2

Input

a

Output

1
a

Hints

  1. Choose the first piece: try every prefix that is a palindrome, shortest first.
  2. Recurse on the rest of the string; when nothing is left, the pieces chosen so far form one partition.

Approach

go(start, pieces): if start == n, record the partition. Otherwise for end from start + 1 to n, if s[start..end) is a palindrome, push it and recurse from end, then pop. Trying shorter pieces first gives exactly the required order. For speed you can precompute isPal[i][j] with DP, but with |s| ≤ 12 a direct check is fine.

Complexity: O(2^n · n) time · O(n) recursion depth

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

string s;
vector<string> pieces, out;

bool isPal(int l, int r) {
    while (l < r)
        if (s[l++] != s[r--]) return false;
    return true;
}

void go(int start) {
    if (start == (int)s.size()) {
        string line;
        for (size_t i = 0; i < pieces.size(); i++) line += (i ? " " : "") + pieces[i];
        out.push_back(line);
        return;
    }
    for (int end = start; end < (int)s.size(); end++) {
        if (!isPal(start, end)) continue;
        pieces.push_back(s.substr(start, end - start + 1));
        go(end + 1);
        pieces.pop_back();
    }
}

int main() {
    cin >> s;
    go(0);
    cout << out.size() << "\n";
    for (auto &l : out) cout << l << "\n";
    return 0;
}

Python solution

s = input().strip()
out = []


def go(start, pieces):
    if start == len(s):
        out.append(" ".join(pieces))
        return
    for end in range(start + 1, len(s) + 1):
        piece = s[start:end]
        if piece == piece[::-1]:
            go(end, pieces + [piece])


go(0, [])
print(len(out))
print("\n".join(out))

Java solution

import java.util.*;

public class Main {
    static String s;
    static List<String> out = new ArrayList<>();

    static boolean isPal(int l, int r) {
        while (l < r)
            if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }

    static void go(int start, String pieces) {
        if (start == s.length()) {
            out.add(pieces);
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (!isPal(start, end)) continue;
            String piece = s.substring(start, end + 1);
            go(end + 1, pieces.isEmpty() ? piece : pieces + " " + piece);
        }
    }

    public static void main(String[] args) {
        s = new Scanner(System.in).next();
        go(0, "");
        StringBuilder sb = new StringBuilder();
        sb.append(out.size()).append('\n');
        for (String l : out) sb.append(l).append('\n');
        System.out.print(sb);
    }
}

Solve Palindrome Partitioning online · All practice problems