Palindrome Partitioning Using Backtracking in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a substring is a palindrome.

DSA Rust

fn is_palindrome(s: &str) -> bool {
    let chars: Vec<char> = s.chars().collect();
    let mut left = 0;
    let mut right = chars.len() - [1];
    while left < right {
        if chars[left] != chars[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}

Drag options to blanks, or click blank then click option'

A0

B2

C1

Dchars.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Using length directly as index causes out-of-bounds error.

Starting right pointer at 0 instead of last index.

We subtract 1 from the length to get the last index because indexing starts at 0.

2fill in blank

medium

Complete the code to push a substring slice into the current partition vector.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Aremove

Bpop

Cclear

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using clear() removes all elements, not just the last.

Using push() instead of removing causes infinite growth.

We use pop() to remove the last added substring after backtracking.

3fill in blank

hard

Fix the error in the for loop range to avoid panic when slicing the string.

DSA Rust

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

Drag options to blanks, or click blank then click option'

As.len() + 1

Bs.len()

Cstart

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using s.len() causes the last character to be excluded.

Using start as end causes empty slices.

The range must go up to s.len() + 1 to include the last character in slicing.

4fill in blank

hard

Fill both blanks to create a recursive backtracking function that partitions the string into palindromes.

DSA Rust

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

Drag options to blanks, or click blank then click option'

As.len()

Bis_palindrome

Cs.len() + 1

Dsubstring.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Using s.len() + 1 causes out-of-range error in Rust slicing.

Checking palindrome incorrectly or missing the function call.

The loop ends at s.len() and we check palindrome using is_palindrome function.

5fill in blank

hard

Fill all three blanks to complete the main function that calls backtracking and returns all palindrome partitions.

DSA Rust

fn partition(s: String) -> Vec<Vec<String>> {
    let mut result = Vec::new();
    let mut current = Vec::new();
    backtrack(&s, [1], &mut current, &mut result);
    [2]
}

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

Drag options to blanks, or click blank then click option'

A0

Bresult

Cs.len()

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from 1 misses the first character.

Returning current instead of result.

Loop ending before full string length.

Start index is 0, return the result vector, and loop ends at s.len().

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