131. Palindrome Partitioning (Medium)

Problem

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

Example

s = "aab" → [["a","a","b"], ["aa","b"]]
s = "a" → [["a"]]

LeetCode 131 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, backtracking with per-cut palindrome check

For each cut point, check whether the left piece is a palindrome; if yes, recurse on the rest.

def partition(s):
    result = []
    path = []

    def is_pal(t):
        return t == t[::-1]                    # L1: O(k) slice + compare

    def backtrack(start):
        if start == len(s):
            result.append(path[:])             # L2: O(n) copy at leaf
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]               # L3: O(k) slice
            if is_pal(piece):
                path.append(piece)             # L4: O(1) push
                backtrack(end)                 # L5: recurse
                path.pop()                     # L6: O(1) pop

    backtrack(0)
    return result

Where the time goes, line by line

Variables: n = len(s), k = substring length.

Line	Per-call cost	Times executed	Contribution
L1/L3 (palindrome check + slice)	$O(k)$ per cut	$O(n · 2^n)$ total cuts	$O(n · 2^n)$
L5 (recurse)	$O(1)$ dispatch	$O(2^n)$ nodes	$O(2^n)$ ← dominates
L2 (copy)	$O(n)$	partitions	$O(n · partitions)$

There are 2^(n-1) possible cut positions, so the search space is $O(2^n)$ . Each call to is_pal for a substring of length k costs $O(k)$ .

Complexity

Time: $O(n · 2^n)$ . For each of 2^(n-1) possible partitions, $O(n)$ palindrome checks.
Space: $O(n)$ recursion.

Swift

final class Solution {
    func partition(_ s: String) -> [[String]] {
        let chars = Array(s); var result: [[String]] = []
        func search(_ start: Int, _ current: [String]) { if start == chars.count { result.append(current); return }; for end in start..<chars.count { let piece = String(chars[start...end]); if Array(piece) == Array(piece.reversed()) { search(end + 1, current + [piece]) } } }
        search(0, []); return result
    }
}

Approach 2: Two-pointer palindrome check (same Big-O, no string slicing)

Avoid slicing by checking the palindrome inline.

def partition(s):
    result = []
    path = []
    n = len(s)

    def is_pal(l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1                      # L1: O(k) two-pointer check
        return True

    def backtrack(start):
        if start == n:
            result.append(path[:])      # L2: O(n) copy
            return
        for end in range(start, n):
            if is_pal(start, end):
                path.append(s[start:end + 1])  # L3: O(k) slice for result
                backtrack(end + 1)             # L4: recurse
                path.pop()

    backtrack(0)
    return result

function partition(s: string): string[][] {
    const result: string[][] = [];
    const path: string[] = [];
    const n = s.length;

    function isPal(l: number, r: number): boolean {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;                                   // L1: O(k) two-pointer check
        }
        return true;
    }

    function backtrack(start: number): void {
        if (start === n) {
            result.push([...path]);                // L2: O(n) copy
            return;
        }
        for (let end = start; end < n; end++) {
            if (isPal(start, end)) {
                path.push(s.slice(start, end + 1)); // L3: O(k) slice for result
                backtrack(end + 1);                 // L4: recurse
                path.pop();
            }
        }
    }

    backtrack(0);
    return result;
}

func partition(s string) [][]string {
    result := [][]string{}
    path := []string{}
    n := len(s)

    isPal := func(l, r int) bool {
        for l < r {
            if s[l] != s[r] { return false }
            l++
            r-- // L1: O(k) two-pointer check
        }
        return true
    }

    var backtrack func(start int)
    backtrack = func(start int) {
        if start == n {
            cp := make([]string, len(path))
            copy(cp, path)
            result = append(result, cp) // L2: O(n) copy
            return
        }
        for end := start; end < n; end++ {
            if isPal(start, end) {
                path = append(path, s[start:end+1]) // L3: O(k) slice for result
                backtrack(end + 1)                  // L4: recurse
                path = path[:len(path)-1]
            }
        }
    }

    backtrack(0)
    return result
}

Where the time goes, line by line

Variables: n = len(s), k = substring length.

Line	Per-call cost	Times executed	Contribution
L1 (two-pointer check)	$O(k)$	$O(n^2)$ pairs	$O(n^2)$ setup
L4 (recurse)	$O(1)$ dispatch	$O(2^n)$ nodes	$O(n · 2^n)$ ← dominates
L2 (copy)	$O(n)$	partitions	$O(n · partitions)$

Complexity

Time: $O(n · 2^n)$ worst case.
Space: $O(n)$ recursion.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func partition(_ s: String) -> [[String]] {
        let chars = Array(s); var result: [[String]] = []
        func palindrome(_ left: Int, _ right: Int) -> Bool { var left = left, right = right; while left < right { if chars[left] != chars[right] { return false }; left += 1; right -= 1 }; return true }
        func search(_ start: Int, _ current: [String]) { if start == chars.count { result.append(current); return }; for end in start..<chars.count where palindrome(start, end) { search(end + 1, current + [String(chars[start...end])]) } }
        search(0, []); return result
    }
}

Approach 3: Precompute palindrome DP table (optimal constant factor)

Precompute is_pal[i][j] for all substrings in $O(n^2)$ . Then the palindrome check during backtracking is $O(1)$ .

def partition(s):
    n = len(s)
    # is_pal[i][j] = True iff s[i:j+1] is a palindrome
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True                        # L1: single chars are palindromes
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True                # L2: O(1) DP recurrence

    result = []
    path = []

    def backtrack(start):
        if start == n:
            result.append(path[:])                 # L3: O(n) copy
            return
        for end in range(start, n):
            if is_pal[start][end]:                 # L4: O(1) table lookup
                path.append(s[start:end + 1])      # L5: O(k) slice for result
                backtrack(end + 1)                 # L6: recurse
                path.pop()

    backtrack(0)
    return result

function partition(s: string): string[][] {
    const n = s.length;
    // isPal[i][j] = true iff s[i..j] is a palindrome
    const isPal: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));
    for (let i = 0; i < n; i++) isPal[i][i] = true;         // L1: single chars
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            if (s[i] === s[j] && (len === 2 || isPal[i + 1][j - 1]))
                isPal[i][j] = true;                          // L2: O(1) DP recurrence
        }
    }

    const result: string[][] = [];
    const path: string[] = [];

    function backtrack(start: number): void {
        if (start === n) {
            result.push([...path]);                          // L3: O(n) copy
            return;
        }
        for (let end = start; end < n; end++) {
            if (isPal[start][end]) {                         // L4: O(1) table lookup
                path.push(s.slice(start, end + 1));          // L5: O(k) slice for result
                backtrack(end + 1);                          // L6: recurse
                path.pop();
            }
        }
    }

    backtrack(0);
    return result;
}

func partition(s string) [][]string {
    n := len(s)
    // isPal[i][j] = true iff s[i:j+1] is a palindrome
    isPal := make([][]bool, n)
    for i := range isPal {
        isPal[i] = make([]bool, n)
        isPal[i][i] = true // L1: single chars are palindromes
    }
    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] && (length == 2 || isPal[i+1][j-1]) {
                isPal[i][j] = true // L2: O(1) DP recurrence
            }
        }
    }

    result := [][]string{}
    path := []string{}

    var backtrack func(start int)
    backtrack = func(start int) {
        if start == n {
            cp := make([]string, len(path))
            copy(cp, path)
            result = append(result, cp) // L3: O(n) copy
            return
        }
        for end := start; end < n; end++ {
            if isPal[start][end] {              // L4: O(1) table lookup
                path = append(path, s[start:end+1]) // L5: O(k) slice for result
                backtrack(end + 1)                   // L6: recurse
                path = path[:len(path)-1]
            }
        }
    }

    backtrack(0)
    return result
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1/L2 (DP table build)	$O(1)$	n^2 cells	$O(n^2)$
L4 ( $O(1)$ lookup)	$O(1)$	$O(n · 2^n)$	$O(n · 2^n)$
L6 (recurse)	$O(1)$ dispatch	$O(2^n)$ nodes	$O(n · 2^n)$ ← dominates

The $O(n^2)$ DP preprocessing pays off when there are many palindrome checks; each one drops from $O(k)$ to $O(1)$ .

Complexity

Time: $O(n · 2^n)$ . The DP table is $O(n^2)$ once; the backtracking work dominates asymptotically but is constant-factor faster.
Space: $O(n^2)$ DP + $O(n)$ recursion.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func partition(_ s: String) -> [[String]] {
        let chars = Array(s), count = s.count; var table = Array(repeating: Array(repeating: false, count: count), count: count)
        for left in stride(from: count - 1, through: 0, by: -1) { for right in left..<count where chars[left] == chars[right] && (right - left < 2 || table[left + 1][right - 1]) { table[left][right] = true } }
        var result: [[String]] = []; func search(_ start: Int, _ current: [String]) { if start == count { result.append(current); return }; for end in start..<count where table[start][end] { search(end + 1, current + [String(chars[start...end])]) } }; search(0, []); return result
    }
}

Summary

Approach	Time	Space
Backtrack + slice palindrome check	$O(n · 2^n)$	$O(n)$
Backtrack + two-pointer check	$O(n · 2^n)$	$O(n)$
Backtrack + precomputed DP	$O(n · 2^n)$	$O(n^2)$

All three have the same dominant term (exponential number of partitions). DP precomputation is the constant-factor win; it’s also how problem 132. Palindrome Partitioning II (min cuts) becomes tractable.

Test cases

def partition(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True
    result = []; path = []
    def backtrack(start):
        if start == n: result.append(path[:]); return
        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end + 1]); backtrack(end + 1); path.pop()
    backtrack(0)
    return result

def _run_tests():
    r = partition("aab")
    assert sorted(map(tuple, r)) == sorted([("a","a","b"), ("aa","b")])
    assert partition("a") == [["a"]]
    # all same characters: every prefix is a palindrome
    r3 = partition("aaa")
    assert sorted(map(tuple, r3)) == sorted([("a","a","a"), ("a","aa"), ("aa","a"), ("aaa",)])
    # single partition only (no internal palindromes)
    r4 = partition("abc")
    assert sorted(map(tuple, r4)) == sorted([("a","b","c")])
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function partition(s: string): string[][] {
    const n = s.length;
    const isPal: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));
    for (let i = 0; i < n; i++) isPal[i][i] = true;
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            if (s[i] === s[j] && (len === 2 || isPal[i + 1][j - 1])) isPal[i][j] = true;
        }
    }
    const result: string[][] = [];
    const path: string[] = [];
    function backtrack(start: number): void {
        if (start === n) { result.push([...path]); return; }
        for (let end = start; end < n; end++) {
            if (isPal[start][end]) {
                path.push(s.slice(start, end + 1));
                backtrack(end + 1);
                path.pop();
            }
        }
    }
    backtrack(0);
    return result;
}

const norm = (arr: string[][]): string =>
    JSON.stringify(arr.map(a => [...a]).sort((a, b) => JSON.stringify(a) < JSON.stringify(b) ? -1 : 1));

console.assert(norm(partition('aab')) === norm([['a','a','b'],['aa','b']]));
console.assert(JSON.stringify(partition('a')) === JSON.stringify([['a']]));
console.assert(norm(partition('aaa')) === norm([['a','a','a'],['a','aa'],['aa','a'],['aaa']]));
console.assert(norm(partition('abc')) === norm([['a','b','c']]));
console.log("all tests pass");

func partition(s string) [][]string {
    n := len(s)
    isPal := make([][]bool, n)
    for i := range isPal {
        isPal[i] = make([]bool, n)
        isPal[i][i] = true
    }
    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] && (length == 2 || isPal[i+1][j-1]) {
                isPal[i][j] = true
            }
        }
    }
    result := [][]string{}
    path := []string{}
    var backtrack func(start int)
    backtrack = func(start int) {
        if start == n {
            cp := make([]string, len(path))
            copy(cp, path)
            result = append(result, cp)
            return
        }
        for end := start; end < n; end++ {
            if isPal[start][end] {
                path = append(path, s[start:end+1])
                backtrack(end + 1)
                path = path[:len(path)-1]
            }
        }
    }
    backtrack(0)
    return result
}

Strings, partitioning at indices
Arrays, the 2D DP palindrome table

Backtracking, the explore, undo, and prune pattern for building candidates.
Sequence DP, the prefix or position state pattern used for strings and ordered arrays.

131. Palindrome Partitioning (Medium)

Problem

Try it yourself

Approach 1: Brute force, backtracking with per-cut palindrome check

Approach 2: Two-pointer palindrome check (same Big-O, no string slicing)

Approach 3: Precompute palindrome DP table (optimal constant factor)

Summary

Test cases

Related data structures

Related concepts