Skip to content

107 — Palindrome Partitioning

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

107 — Palindrome Partitioning

LeetCode 131 · Medium. Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.

🍽️ Intuition

A partition of a string is just a choice of where to place the cuts between characters — every gap between two adjacent characters is either a cut or it isn't. That's the same "include / exclude" branching from Subsets, just applied to gaps instead of elements. The palindrome constraint is what makes most cut-placements invalid: a valid partition is one where every single piece, not just the whole string, reads the same forwards and backwards.

🚩 Pattern-Recognition Cue

"Partition s such that every substring is a palindrome, return all possible partitionings" is the cue: "all possible partitionings satisfying a per-piece constraint" is a search over where to place cuts, pruned by a validity check (isPalindrome) that can be tested on a partial candidate the moment a piece is proposed, rather than only after the whole string is fully cut up.

🐢 Brute Force

Enumerate all 2^(n-1) ways to place cut points between the n characters, build each complete partition first, and only check afterward whether every resulting piece happens to be a palindrome.

func partitionBruteForce(_ s: String) -> [[String]] {
    let chars = Array(s)
    let n = chars.count
    guard n > 0 else { return [[]] }

    func isPalindrome(_ str: [Character]) -> Bool {
        var left = 0
        var right = str.count - 1
        while left < right {
            if str[left] != str[right] { return false }
            left += 1
            right -= 1
        }
        return true
    }

    var results: [[String]] = []

    for mask in 0..<(1 << (n - 1)) {
        var cutPoints = [0]
        for i in 0..<(n - 1) where mask & (1 << i) != 0 {
            cutPoints.append(i + 1)
        }
        cutPoints.append(n)

        var pieces: [[Character]] = []
        for i in 0..<cutPoints.count - 1 {
            pieces.append(Array(chars[cutPoints[i]..<cutPoints[i + 1]]))   // build the FULL partition first
        }

        if pieces.allSatisfy(isPalindrome) {   // only checked after every piece already exists
            results.append(pieces.map { String($0) })
        }
    }

    return results
}

// smoke test
print(partitionBruteForce("aab").count)   // 2
print(partitionBruteForce("a"))            // [["a"]]
print(partitionBruteForce(""))             // [[]]

Big-O: O(n · 2^n) time — 2^(n-1) cut patterns, each requiring O(n) work to slice the string into pieces and check every one for palindrome-ness, even patterns where the very first piece is obviously not a palindrome.

🚀 Optimal

Extend the current partition one piece at a time, and only recurse into a candidate piece if it's already a palindrome — a non-palindromic prefix is discarded the instant it's proposed, never mind what cuts might come after it.

func partition(_ s: String) -> [[String]] {
    let chars = Array(s)
    var results: [[String]] = []
    var path: [String] = []

    func isPalindrome(_ left: Int, _ right: Int) -> Bool {
        var l = left, r = right
        while l < r {
            if chars[l] != chars[r] { return false }
            l += 1
            r -= 1
        }
        return true
    }

    func backtrack(_ start: Int) {
        if start == chars.count {
            results.append(path)
            return
        }

        for end in start..<chars.count {
            if !isPalindrome(start, end) { continue }   // prune: skip non-palindromic prefixes immediately

            path.append(String(chars[start...end]))
            backtrack(end + 1)
            path.removeLast()
        }
    }

    backtrack(0)
    return results
}

// smoke test — same cases as the brute force
print(partition("aab"))   // [["a", "a", "b"], ["aa", "b"]]
print(partition("a"))      // [["a"]]
print(partition(""))       // [[]]

Big-O: O(n · 2^n) in the theoretical worst case (a string like "aaaa...a" genuinely has exponentially many palindromic partitions), but every non-palindromic prefix is discarded with an O(n) check before any recursive call is made for it — no wasted recursion building pieces that were never going to survive.

🔑 The Key Insight

Like Word Search, this is a case where the worst-case Big-O doesn't move — a string of all-identical characters really does have exponentially many valid partitions, and no amount of pruning changes that. The gap is in how much work gets spent on the invalid candidates along the way. The brute force finds out a piece was invalid only after cutting the entire rest of the string around it. The optimal version checks each proposed piece the moment it's proposed, so a single bad prefix — say, the very first two characters not matching — prunes every partition that would have started with that prefix, all at once, instead of discovering the same failure once per doomed partition.

🔗 Related Chapters

  • DFS and Backtracking — the same choose/recurse/un-choose skeleton, extending path by one validated piece at a time instead of one array element.
  • Two Pointers — isPalindrome is a two-pointer scan inward from both ends of the candidate piece, the same technique used throughout that chapter.
  • Arrays and Strings — s is converted to [Character] up front so indexing and slicing are O(1)-per-access instead of walking Swift's grapheme-aware String.Index.

🧸 Memory Sentence

Palindrome Partitioning is "cut, but only where the piece behind you is already a palindrome" — check each piece the moment you propose it, instead of cutting the whole string first and hoping.

✅ Check Your Understanding

  1. partition("aaaa") has more than two results. Sketch (or trace) enough of the recursion tree to see why the number of valid partitions of an all-identical-character string grows exponentially.
  2. Why does backtrack check isPalindrome(start, end) inside the loop, before appending to path, rather than appending first and checking the whole path for validity at the base case?
  3. partition("") returns [[]]. What does that empty-list-of-pieces represent, and why is it the correct answer rather than [] (no partitions at all)?

⬅️ Previous: Word Search · Next: Letter Combinations of a Phone Number ➡️

Clone this wiki locally