Backtracking/Palindrome PartitioningMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Palindrome Partitioning

Backtracking·Medium

Given a string s, return all possible ways to partition it such that every substring in the partition is a palindrome.

A palindrome reads the same forwards and backwards. A partition of a string is a list of non-empty substrings that concatenate to the original string.

Use backtracking: at each position try every suffix that is a palindrome, add it to the current path, recurse on the remaining suffix, and remove it on the way out.

For deterministic comparison, sort the outer list of partitions lexicographically (compare element-by-element across the string arrays).

Examples

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

"aab" can be split as ["a","a","b"] (each is a palindrome) or ["aa","b"] (aa and b are palindromes).

Input: s = "a"

Output: [["a"]]

Input: s = "aba"

Output: [["a","b","a"],["aba"]]

Constraints

1 <= s.length <= 16
s consists only of lowercase English letters.

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Backtracking
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.