Palindrome Partitioning

MEDIUM✓ CHIP-TIMEDLC #131 — FULL STATEMENT ↗

The drill: Slice a string into pieces, left to right, so that every piece by itself reads the same forwards and backwards — return every way to slice it.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string arrives, and the task is to cut it into consecutive pieces, left to right, so every resulting piece reads identically forwards and backwards on its own.

Every character must land in exactly one piece — no character skipped, none reused — and every one of the possibly many valid ways to cut the string counts as a separate result.

A single character is always a valid palindrome on its own, so a partition where every piece is one character long is always a legal, if usually unremarkable, answer.

EX 01

s = "a"

→ [["a"]]

MINIMUM SIZE, SINGLE CHARACTER

EX 02

s = "ab"

→ [["a", "b"]]

NO PALINDROME LONGER THAN ONE CHARACTER

EX 03

s = "aa"

→ [["a", "a"], ["aa"]]

strings are short, generally under twenty characters
every cut piece must itself be a palindrome
every character of the string belongs to exactly one piece
all valid partitions are returned, order between them is free

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every partition is just a set of cut points among the gaps between characters — the question is which cuts keep every resulting piece a palindrome.

HINT 2 THE STRUCTURE

Extend the current piece one character at a time from wherever the last cut left off. The moment a piece stops being a palindrome, there's no reason to extend it further or use it as a stepping stone.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack from index start: try every end from start + 1 to the string's length, and only recurse past end when s[start:end] is a palindrome. Reaching the end of the string means the current path is a full partition.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PRUNE-EARLY CUTPATTERN · BACKTRACK, PRUNE NON-PALINDROMESs = "aba"

STEP 1

String 'aba'. Grow each piece from the last cut; only recurse past a piece once it's already a palindrome.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/palindrome-partitioning.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        res = []
        path = []

        def is_pal(sub):
            return sub == sub[::-1]

        def backtrack(start):
            if start == n:
                res.append(list(path))
                return
            for end in range(start + 1, n + 1):
                piece = s[start:end]
                if is_pal(piece):        # prune — never step into a bad prefix
                    path.append(piece)
                    backtrack(end)
                    path.pop()

        backtrack(0)
        return res

TIME O(2ⁿ·N)SPACE O(N)PYTHON · RACE PACE · 22 LN

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        res = []
        for mask in range(1 << (n - 1)):        # every gap between characters, cut or not
            cuts = [i + 1 for i in range(n - 1) if mask & (1 << i)]
            pieces = []
            prev = 0
            for cut in cuts:
                pieces.append(s[prev:cut])
                prev = cut
            pieces.append(s[prev:])
            if all(p == p[::-1] for p in pieces):
                res.append(pieces)
        return res

TIME O(2ⁿ·N)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String piece = s.substring(start, end);
            if (isPalindrome(piece)) {
                path.add(piece);
                backtrack(s, end, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    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;
    }
}

TIME O(2ⁿ·N)SPACE O(N)JAVA · RACE PACE · 34 LN

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>> res = new ArrayList<>();
        int total = 1 << (n - 1);
        for (int mask = 0; mask < total; mask++) {
            List<Integer> cuts = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) {
                if ((mask & (1 << i)) != 0) {
                    cuts.add(i + 1);
                }
            }
            List<String> pieces = new ArrayList<>();
            int prev = 0;
            for (int cut : cuts) {
                pieces.add(s.substring(prev, cut));
                prev = cut;
            }
            pieces.add(s.substring(prev));
            boolean allPal = true;
            for (String p : pieces) {
                if (!isPalindrome(p)) {
                    allPal = false;
                    break;
                }
            }
            if (allPal) {
                res.add(pieces);
            }
        }
        return res;
    }

    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;
    }
}

TIME O(2ⁿ·N)SPACE O(N)JAVA · TRAINING PACE · 45 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED