DSA problem
Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s. A palindrome is a string that reads the same forwards and backwards (single characters and the empty string both count).
For example, s = "aab" can be partitioned as ["a", "a", "b"] (three palindromes of length 1) or ["aa", "b"] (one palindrome of length 2 followed by one of length 1). The complete answer is the set of all valid such partitions.
The cleanest formulation is backtracking with a start index. At each recursive call we try every end from start to n - 1; if the substring s[start..end] is a palindrome, we add it to the current partition, recurse with the new start at end + 1, and undo. When start == n we have consumed the entire string and the current partition is a valid one, so we snapshot it into the results.
For speed we precompute a palindrome DP table isPal[i][j] in O(n^2) time and space: isPal[i][j] is true if s[i..j] is a palindrome, computed bottom-up using the recurrence isPal[i][j] = (s[i] == s[j]) && (j - i < 2 || isPal[i + 1][j - 1]). This turns each palindrome check inside the recursion into an O(1) lookup. Total time is bounded by O(n * 2^n) because there are up to 2^(n - 1) partitions and each costs O(n) to materialize.
Examples
s = "aab"[["a","a","b"],["aa","b"]]s = "a"[["a"]]s = "aaba"[["a","a","b","a"],["a","aba"],["aa","b","a"]]Constraints
- 1 <= s.length <= 16
- s contains only lowercase English letters.
- The output may be returned in any order.
- Every substring in a returned partition must be a palindrome.
- Adjacent substrings in a partition together cover `s` with no overlap.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.