1. Whole string cut
Reaching the end means every piece in the path is a palindrome.
if (start === s.length)Typorithm · medium
Palindrome Partitioning
▷ Interactive algorithm labpalindrome-partitioningbacktrackingsubstring-cutspalindrome-checkchoose-explore-undo
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Palindrome Partitioning
Backtracking
Cut the string at every position where the prefix is a palindrome, then recurse on the rest.
A partition splits the string into pieces that are each palindromes.
At each start, try every end; only recurse when the substring start..end is a palindrome.
Reaching the string's end means the current path is a complete valid partition.
Preparing algorithm lab…
01
Cut only palindromic prefixes.
02
Recurse on the remaining suffix.
03
Base case: start reaches the end.
function partition(s) {
const result = [];
function isPalindrome(left, right) {
while (left < right) {
if (s[left] !== s[right]) return false;
left += 1;
right -= 1;
}
return true;
}
function backtrack(start, path) {
if (start === s.length) {
result.push([...path]);
return;
}
for (let end = start; end < s.length; end += 1) {
if (!isPalindrome(start, end)) continue;
path.push(s.slice(start, end + 1));
backtrack(end + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Try each cut
Each end position is a candidate cut point for the next piece.
for (let end = start; end < s.length; end += 1)3. Skip non-palindrome
Only cut a piece that is itself a palindrome.
if (!isPalindrome(start, end)) continue4. Choose piece
Add the palindromic substring to the current partition.
path.push(s.slice(start, end + 1))5. Undo
Remove the piece to try a different cut.
path.pop()A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.