Palindrome Partitioning Using Backtracking in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Partitioning for "aab"

What is the output of the following Rust code that finds all palindrome partitions of the string "aab"?

DSA Rust

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

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

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

fn main() {
    let partitions = partition("aab");
    println!("{:?}", partitions);
}

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

B [["a", "ab"], ["aa", "b"]]

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

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

💡 Hint

Check all substrings and verify if they read the same forwards and backwards.

The code finds all ways to split the string "aab" into substrings that are palindromes. "a", "a", "b" and "aa", "b" are the valid palindrome partitions.

🧠 Conceptual

intermediate

Number of Palindrome Partitions for "abc"

How many palindrome partitions does the string "abc" have?

A 2

B 3

C 1

D 4

💡 Hint

Each single character is a palindrome. Check if any longer substring is palindrome.

Only the partition with each character alone is palindrome: ["a", "b", "c"]. No longer substrings like "ab" or "bc" or "abc" are palindromes.

🔧 Debug

advanced

Identify the Error in Palindrome Partitioning Code

What error will this Rust code produce when run?

DSA Rust

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

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

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

fn main() {
    let partitions = partition("aab");
    println!("{:?}", partitions);
}

A Stack overflow due to infinite recursion

B Index out of bounds panic

C Compilation error: mismatched types

D No error, prints correct partitions

💡 Hint

Check the base case condition for recursion termination.

The base case uses 'start > s.len()', but start can equal s.len() to stop. Using '>' causes infinite recursion leading to stack overflow.

❓ Predict Output

advanced

Output of Palindrome Partitioning for "aaa"

What is the output of the following Rust code that finds all palindrome partitions of the string "aaa"?

DSA Rust

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

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

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

fn main() {
    let partitions = partition("aaa");
    println!("{:?}", partitions);
}

A [["aaa"]]

B [["a", "a", "a"], ["a", "aa"], ["aa", "a"], ["aaa"]]

C [["a", "a", "a"]]

D [["a", "aa"], ["aa", "a"]]

💡 Hint

Consider all palindrome substrings including single and multiple characters.

All partitions where each substring is palindrome are: single letters, pairs "aa", and the whole "aaa".

🧠 Conceptual

expert

Time Complexity of Palindrome Partitioning Using Backtracking

What is the time complexity of the palindrome partitioning algorithm using backtracking on a string of length n?

A O(n!)

B O(n^3)

C O(2^n)

D O(n * 2^n)

💡 Hint

Consider the number of partitions and palindrome checks.

There are up to 2^(n-1) ways to partition a string. Each palindrome check can take O(n). So total is O(n * 2^n).

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