Palindrome Partitioning Using Backtracking in DSA Rust - Build from Scratch

Palindrome Partitioning Using Backtracking

📖 Scenario: Imagine you have a word, and you want to split it into parts where each part reads the same forwards and backwards. This is called palindrome partitioning. For example, the word "noon" can be split as "n" | "oo" | "n" or "noon" itself.

🎯 Goal: You will build a program that finds all the ways to split a given word into palindrome parts using backtracking. This helps understand how to explore all possible splits and check palindrome conditions.

📋 What You'll Learn

Create a string variable with a specific word

Create a helper function to check if a substring is a palindrome

Use backtracking to find all palindrome partitions

Print all palindrome partitions as lists of strings

💡 Why This Matters

🌍 Real World

Palindrome partitioning helps in text processing tasks like DNA sequence analysis, data compression, and pattern recognition.

💼 Career

Understanding backtracking and palindrome checks is useful for software engineers working on algorithms, coding interviews, and complex problem solving.

1

Create the input string

Create a variable called input_word and set it to the string "aab".

DSA Rust

# Create a variable called input_word and set it to "aab"
# Your code here

Hint

Use let input_word = "aab"; to create the string variable.

2

Write a palindrome check function

Write a function called is_palindrome that takes a string slice s: &str and returns bool. It should return true if s reads the same forwards and backwards, otherwise false.

DSA Rust

let input_word = "aab";
// Write the is_palindrome function below
// Your code here

Hint

Use s.chars().eq(s.chars().rev()) to check palindrome.

3

Implement backtracking to find palindrome partitions

Write a function called backtrack that takes these parameters: s: &str, start: usize, current_partition: &mut Vec, and result: &mut Vec>. Use backtracking to find all palindrome partitions of s starting from start. For each substring from start to end, if it is a palindrome, add it to current_partition, recurse from end + 1, then remove the last substring to backtrack.

DSA Rust

let input_word = "aab";

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

// Write the backtrack function below
// Your code here

Hint

Use a for loop from start to s.len() and check palindrome substrings.

4

Run backtracking and print all palindrome partitions

Create a mutable vector called result to store all partitions. Create a mutable vector called current_partition for the current path. Call backtrack with input_word, 0, &mut current_partition, and &mut result. Then print result.

DSA Rust

let input_word = "aab";

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

fn backtrack(s: &str, start: usize, current_partition: &mut Vec, result: &mut Vec>) {
    if start == s.len() {
        result.push(current_partition.clone());
        return;
    }

    for end in start..s.len() {
        let substring = &s[start..=end];
        if is_palindrome(substring) {
            current_partition.push(substring.to_string());
            backtrack(s, end + 1, current_partition, result);
            current_partition.pop();
        }
    }
}

// Create result and current_partition vectors, call backtrack, and print result
// Your code here

Hint

Remember to create result and current_partition as mutable vectors, call backtrack, then print result.

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