Palindrome Partitioning Using Backtracking in DSA Rust

Mental Model

We want to split a string into parts where each part reads the same forwards and backwards. We try all splits step by step and keep only the ones that work.

Analogy: Imagine cutting a ribbon into pieces where each piece is a perfect mirror image of itself. You try cutting at different points and keep the cuts that make all pieces symmetrical.

s = "a b a c"
Indices: 0 1 2 3
Partitions: ["a", "b", "a", "c"] or ["aba", "c"]
We explore cuts between letters:
 a | b | a | c
 ↑   ↑   ↑   ↑
Try cuts at each ↑ to check palindrome parts.

Dry Run Walkthrough

Input: string: "aab"

Goal: Find all ways to split "aab" so every part is a palindrome

Step 1: Start from index 0, check substring "a" (0 to 0) is palindrome

["a"] + remaining "ab" to partition

Why: We try the smallest piece first to build partitions step by step

Step 2: From index 1, check substring "a" (1 to 1) is palindrome

["a", "a"] + remaining "b" to partition

Why: Continue partitioning the rest after first palindrome

Step 3: From index 2, check substring "b" (2 to 2) is palindrome

["a", "a", "b"] + no remaining string

Why: Reached end with all palindrome parts, save this partition

Step 4: Backtrack to index 1, check substring "ab" (1 to 2) is not palindrome, skip

["a"] + remaining "ab" to partition

Why: Skip invalid palindrome to avoid wrong partitions

Step 5: Backtrack to index 0, check substring "aa" (0 to 1) is palindrome

["aa"] + remaining "b" to partition

Why: Try longer palindrome from start

Step 6: From index 2, check substring "b" (2 to 2) is palindrome

["aa", "b"] + no remaining string

Why: Reached end with all palindrome parts, save this partition

Result:

["a", "a", "b"]
["aa", "b"]

Annotated Code

DSA Rust

fn is_palindrome(s: &str) -> bool {
    let bytes = s.as_bytes();
    let mut left = 0;
    let mut right = bytes.len().saturating_sub(1);
    while left < right {
        if bytes[left] != bytes[right] {
            return false; // mismatch means not palindrome
        }
        left += 1; // move inward from left
        right = right.saturating_sub(1); // move inward from right
    }
    true // all matched, palindrome
}

fn backtrack(s: &str, start: usize, path: &mut Vec<String>, result: &mut Vec<Vec<String>>) {
    if start == s.len() {
        result.push(path.clone()); // reached end, save current partition
        return;
    }
    for end in start + 1..=s.len() {
        let substring = &s[start..end];
        if is_palindrome(substring) {
            path.push(substring.to_string()); // choose this palindrome
            backtrack(s, end, path, result); // explore further
            path.pop(); // backtrack to try other partitions
        }
    }
}

fn palindrome_partitioning(s: String) -> Vec<Vec<String>> {
    let mut result = Vec::new();
    let mut path = Vec::new();
    backtrack(&s, 0, &mut path, &mut result);
    result
}

fn main() {
    let input = "aab".to_string();
    let partitions = palindrome_partitioning(input);
    for partition in partitions {
        println!("{:?}", partition);
    }
}

if bytes[left] != bytes[right] { return false; }

check mismatch to detect non-palindrome substring

while left < right { left += 1; right = right.saturating_sub(1); }

move pointers inward to compare characters

if start == s.len() { result.push(path.clone()); return; }

if reached end of string, save current palindrome partition

for end in start + 1..=s.len() { let substring = &s[start..end]; if is_palindrome(substring) { ... } }

try all substrings from current start, proceed only if palindrome

path.push(substring.to_string()); backtrack(s, end, path, result); path.pop();

choose substring, recurse deeper, then undo choice to explore others

Output

["a", "a", "b"]

["aa", "b"]

Complexity Analysis

Time: O(n * 2^n) because we try all partitions and check palindrome for each substring

Space: O(n) for recursion stack and current path storage

vs Alternative: Naive approach tries all partitions without pruning, which is slower; backtracking prunes by checking palindrome early

Edge Cases

empty string

returns empty list of partitions

DSA Rust

if start == s.len() { result.push(path.clone()); return; }

string with all identical characters, e.g. "aaa"

returns all possible palindrome partitions including single chars and longer palindromes

DSA Rust

if is_palindrome(substring) { ... }

string with no palindrome longer than 1, e.g. "abc"

returns partitions with single characters only

DSA Rust

if is_palindrome(substring) { ... }

When to Use This Pattern

When asked to find all ways to split a string into palindrome parts, use backtracking to explore all partitions and prune invalid ones early.

Common Mistakes

Mistake: Not checking palindrome before recursing, causing unnecessary work
Fix: Add palindrome check before recursive call to prune invalid partitions

Mistake: Not backtracking (not removing last chosen substring), causing wrong results
Fix: Pop last substring after recursive call to restore state for next tries

Summary

Splits a string into all possible palindrome partitions using backtracking.

Use when you need to find all palindrome-based splits of a string.

The key is to try every cut and only continue if the current piece is a palindrome.

Practice

1. What is the main goal of palindrome partitioning using backtracking?

easy

A. To split a string into all possible palindrome substrings

B. To find the longest palindrome substring in a string

C. To count the number of palindromes in a string

D. To reverse the string and check if it is a palindrome

Solution

1. Step 1: Understand palindrome partitioning using backtracking

   Palindrome partitioning means dividing a string into parts where each part is a palindrome. Backtracking helps explore all possible ways to split the string into palindrome parts.

2. Final Answer:

   To split a string into all possible palindrome substrings -> Option A

3. Quick Check:

   Palindrome partitioning = all palindrome splits [OK]

Hint: Backtracking explores all palindrome splits [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it only counts palindromes
• Assuming it just reverses the string

2. Which Rust syntax correctly defines a function to check if a string slice is a palindrome?

easy

A. fn is_palindrome(s: &str) -> bool { s.chars().eq(s.chars().rev()) }

B. fn is_palindrome(s: String) -> bool { s == s.reverse() }

C. fn is_palindrome(s: &str) -> bool { s == s.reverse() }

D. fn is_palindrome(s: String) -> bool { s.chars().eq(s.chars()) }

Solution

1. Step 1: Check function signature and verify palindrome logic

   Using &str is efficient for string slices without ownership transfer. Comparing characters iterator with its reverse checks palindrome correctly.

2. Final Answer:

   fn is_palindrome(s: &str) -> bool { s.chars().eq(s.chars().rev()) } -> Option A

3. Quick Check:

   Correct Rust palindrome check syntax = fn is_palindrome(s: &str) -> bool { s.chars().eq(s.chars().rev()) } [OK]

Hint: Use &str and compare chars with reversed chars [OK]

Common Mistakes:

• Using String instead of &str unnecessarily
• Calling reverse() method which does not exist on String
• Comparing string to itself without reversing

3. What will be the output of the following Rust code snippet?

fn main() {
    let s = "aab";
    let mut result = vec![];
    fn backtrack(s: &str, start: usize, path: &mut Vec<String>, result: &mut Vec) {
        if start == s.len() {
            result.push(path.clone());
            return;
        }
        for end in start+1..=s.len() {
            let substr = &s[start..end];
            if substr.chars().eq(substr.chars().rev()) {
                path.push(substr.to_string());
                backtrack(s, end, path, result);
                path.pop();
            }
        }
    }
    backtrack(s, 0, &mut vec![], &mut result);
    println!("{:?}", result);
}

medium

A. [["a", "ab"]]

B. [["aab"]]

C. [["a", "a", "b"], ["aa", "b"]]

D. [["aa", "bb"]]

Solution

1. Step 1: Trace backtracking on "aab"

   Partitions are checked for palindrome substrings starting from index 0. "a" is palindrome, then "a" again, then "b"; also "aa" is palindrome, then "b". Output: [["a", "a", "b"], ["aa", "b"]].

2. Final Answer:

   [["a", "a", "b"], ["aa", "b"]] -> Option C

3. Quick Check:

   All palindrome splits of "aab" = [["a", "a", "b"], ["aa", "b"]] [OK]

Hint: Check all palindrome substrings from each start index [OK]

Common Mistakes:

• Missing the "aa" palindrome substring
• Including non-palindrome substrings like "ab"
• Confusing output format

4. Identify the bug in this Rust backtracking function for palindrome partitioning:

fn backtrack(s: &str, start: usize, path: &mut Vec<String>, result: &mut Vec) {
    if start > s.len() {
        result.push(path.clone());
        return;
    }
    for end in start+1..=s.len() {
        let substr = &s[start..end];
        if substr.chars().eq(substr.chars().rev()) {
            path.push(substr.to_string());
            backtrack(s, end, path, result);
            path.pop();
        }
    }
}

medium

A. The for loop range should be start..=s.len(), not start+1..=s.len()

B. The path vector should not be cloned when pushing to result

C. The substring check should use bytes instead of chars

D. The base case condition should be start == s.len(), not start > s.len()

Solution

1. Step 1: Analyze base case and why it fails

   Backtracking ends when start reaches string length exactly, not greater. If start > s.len(), it means out of bounds, so base case never triggers correctly.

2. Final Answer:

   The base case condition should be start == s.len(), not start > s.len() -> Option D

3. Quick Check:

   Base case must match string length exactly [OK]

Hint: Base case triggers at start == string length [OK]

Common Mistakes:

• Using start > s.len() causes missed base case
• Changing loop range incorrectly
• Unnecessary cloning or wrong substring checks

5. Given the string "aaaaa", how many palindrome partitions will the backtracking algorithm find if it returns all possible palindrome partitions?

hard

A. 8

B. 16

C. 20

D. 12

Solution

1. Step 1: Analyze all-'a' string partitions

   Since all characters are identical 'a', every substring is a palindrome. The number of partitions equals the ways to place cuts in the 4 gaps between 5 characters: 2^4 = 16.

2. Final Answer:

   16 -> Option B

3. Quick Check:

   2^{n-1} = 16 for n=5 [OK]

Hint: For identical chars string, 2^{n-1} partitions [OK]

Common Mistakes:

• Counting only large palindrome substrings
• Ignoring smaller palindrome partitions
• Underestimating total partition count