131. Palindrome Partitioning

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: High
LeetCode: 131

Quick Sights

Time Complexity: isPalindrome from the optimal approach.
Space Complexity: pal[left][right] from the optimal approach.
Core Mechanism: Partition string s into substrings such that every piece is a palindrome; return all such partitions.

Concept Explanation

Partition string s into substrings such that every piece is a palindrome; return all such partitions.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

All valid splits — backtracking
Palindrome check each candidate prefix — precompute DP table for speed

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute — check palindrome by substring scan each time — O(n * 2^n) worse constant.
Optimal — DFS + isPalindrome memo or DP table pal[left][right] — same asymptotic, faster checks.

Optimal Solution

Go

func partition(s string) [][]string {
	result := [][]string{}
	path := make([]string, 0, len(s))

	var isPalindrome func(left int, right int) bool
	isPalindrome = func(left int, right int) bool {
		for left < right {
			if s[left] != s[right] {
				return false
			}
			left++
			right--
		}
		return true
	}

	var dfs func(start int)
	dfs = func(start int) {
		if start == len(s) {
			copied := make([]string, len(path))
			copy(copied, path)
			result = append(result, copied)
			return
		}
		for end := start + 1; end <= len(s); end++ {
			if isPalindrome(start, end-1) {
				path = append(path, s[start:end])
				dfs(end)
				path = path[:len(path)-1]
			}
		}
	}
	dfs(0)
	return result
}

JavaScript

function partition(s) {
  const result = [];
  const path = [];

  function isPalindrome(left, right) {
    while (left < right) {
      if (s[left] !== s[right]) {
        return false;
      }
      left += 1;
      right -= 1;
    }
    return true;
  }

  function dfs(startIndex) {
    if (startIndex === s.length) {
      result.push([...path]);
      return;
    }
    for (let endIndex = startIndex + 1; endIndex <= s.length; endIndex += 1) {
      if (isPalindrome(startIndex, endIndex - 1)) {
        path.push(s.slice(startIndex, endIndex));
        dfs(endIndex);
        path.pop();
      }
    }
  }

  dfs(0);
  return result;
}