Every Way to Split a String Into Palindromic Pieces

Medium20–25 min

Topics

BacktrackingRecursionString

Companies

AmazonGoogleUber

Given a string s, find every way to cut it into consecutive pieces so that each individual piece reads the same forwards and backwards. A single character always qualifies on its own, so at minimum the all-single-character split always works — the question is which other, coarser splits also happen to work. Trying every possible cut pattern and validating the resulting partition afterward finds every answer, but it builds and discards a lot of doomed partitions along the way — one non-palindromic piece anywhere invalidates the whole thing, yet that's only discovered once every piece has already been carved out. Checking each piece the moment it's proposed, before it's ever added to the path, means a doomed choice costs only the check itself — nothing gets built around it first.

Test Case 1:

Input:s = "abba"

Output:[["a", "b", "b", "a"], ["a", "bb", "a"], ["abba"]]

Explanation:Three ways to cut "abba" so every piece reads the same forwards and backwards.

Test Case 2:

Input:s = "xyz"

Output:[["x", "y", "z"]]

Explanation:No two adjacent (or further) characters match, so single letters are the only palindromic pieces available — there's exactly one valid split.

Test Case 3:

Input:s = "q"

Output:[["q"]]

Explanation:A single character is always its own palindrome.

Constraints

◆1 ≤ s.length ≤ 8
◆s consists only of lowercase English letters
◆Results are returned sorted (each partition compared element-by-element, shorter first on a tie) for a stable, checkable answer

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Try Every Cut Pattern, Validate the Whole Partition

Brute

Between n characters there are n-1 possible cut points, and each one is independently either "cut here" or "don't" — a bitmask over those n-1 gaps enumerates every possible way to slice the string, 2ⁿ⁻¹ of them. Build the resulting pieces for each mask, then check every piece for being a palindrome only once the whole partition already exists. This finds every valid answer, but a partition with even one non-palindromic piece is still fully built out of substrings before that piece gets checked and the whole thing thrown away.

TimeO(2ⁿ · n)

SpaceO(2ⁿ · n)

Java

Try it out

class Solution {
    public String[][] allPalindromicPartitions(String s) {
        int n = s.length();
        int gaps = n - 1;
        List<String[]> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << gaps); mask++) {
            List<String> pieces = new ArrayList<>();
            int start = 0;
            for (int g = 0; g < gaps; g++) {
                if ((mask & (1 << g)) != 0) {
                    pieces.add(s.substring(start, g + 1));
                    start = g + 1;
                }
            }
            pieces.add(s.substring(start));
            boolean allPalindromes = true;
            for (String piece : pieces) {
                if (!isPalindrome(piece)) {
                    allPalindromes = false;
                    break;
                }
            }
            if (allPalindromes) {
                result.add(pieces.toArray(new String[0]));
            }
        }
        Collections.sort(result, (a, b) -> {
            int len = Math.min(a.length, b.length);
            for (int i = 0; i < len; i++) {
                int cmp = a[i].compareTo(b[i]);
                if (cmp != 0) return cmp;
            }
            return a.length - b.length;
        });
        return result.toArray(new String[0][]);
    }

    private boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

Optimal — Try Each Next Piece, Validate Before Recursing

Optimal

Build a partition left to right: at the current position, try every possible length for the next piece, but check whether that specific piece is a palindrome immediately — only if it passes does the search extend into it. A prefix that instantly fails, like the "c" onward in "ca", is rejected right there and never gets appended to the path or explored any further, unlike the brute-force version which builds a complete partition around it first. Every branch this search ever enters is one built entirely out of confirmed palindromic pieces.