Valid Palindrome Two Pointer in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Pointer Palindrome Check

What is the output of this Rust code that checks if a string is a palindrome ignoring non-alphanumeric characters and case?

DSA Rust

fn is_palindrome(s: &str) -> bool {
    let s = s.to_lowercase();
    let bytes = s.as_bytes();
    let (mut left, mut right) = (0, bytes.len() - 1);
    while left < right {
        if !bytes[left].is_ascii_alphanumeric() {
            left += 1;
            continue;
        }
        if !bytes[right].is_ascii_alphanumeric() {
            right -= 1;
            continue;
        }
        if bytes[left] != bytes[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}

fn main() {
    let test_str = "A man, a plan, a canal: Panama";
    println!("{}", is_palindrome(test_str));
}

A false

B true

C Compilation error

D Runtime panic

💡 Hint

Think about how the two pointers skip non-alphanumeric characters and compare letters ignoring case.

The code converts the string to lowercase and uses two pointers to compare characters from start and end, skipping non-alphanumeric characters. The given string is a well-known palindrome phrase ignoring punctuation and case, so the function returns true.

❓ Predict Output

intermediate

Result of Palindrome Check on Non-Palindrome String

What will the output be when running this Rust palindrome check code on the string "Hello, World!"?

DSA Rust

fn is_palindrome(s: &str) -> bool {
    let s = s.to_lowercase();
    let bytes = s.as_bytes();
    let (mut left, mut right) = (0, bytes.len() - 1);
    while left < right {
        if !bytes[left].is_ascii_alphanumeric() {
            left += 1;
            continue;
        }
        if !bytes[right].is_ascii_alphanumeric() {
            right -= 1;
            continue;
        }
        if bytes[left] != bytes[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}

fn main() {
    let test_str = "Hello, World!";
    println!("{}", is_palindrome(test_str));
}

A false

B Compilation error

C Runtime panic

D true

💡 Hint

Check if the characters match when ignoring punctuation and case.

The string "Hello, World!" is not a palindrome because the characters do not match when compared from start and end ignoring punctuation and case. The function returns false.

🔧 Debug

advanced

Identify the Bug in Palindrome Two Pointer Code

This Rust code attempts to check if a string is a palindrome ignoring non-alphanumeric characters and case. What error will it produce when run?

DSA Rust

fn is_palindrome(s: &str) -> bool {
    let s = s.to_lowercase();
    let bytes = s.as_bytes();
    let (mut left, mut right) = (0, bytes.len());
    while left < right {
        if !bytes[left].is_ascii_alphanumeric() {
            left += 1;
            continue;
        }
        if !bytes[right].is_ascii_alphanumeric() {
            right -= 1;
            continue;
        }
        if bytes[left] != bytes[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}

fn main() {
    let test_str = "racecar";
    println!("{}", is_palindrome(test_str));
}

A Returns true correctly

B Compilation error

C Index out of bounds panic

D Returns false incorrectly

💡 Hint

Check how the right pointer is initialized and used.

The right pointer is initialized to bytes.len(), which is one past the last valid index. Accessing bytes[right] causes an index out of bounds panic at runtime.

🧠 Conceptual

advanced

Why Use Two Pointers for Palindrome Check?

Why is the two pointer technique efficient for checking if a string is a palindrome ignoring non-alphanumeric characters and case?

A It converts the string to a number and checks if the number is a palindrome.

B It sorts the string first to compare characters easily.

C It uses recursion to compare characters from the middle outwards.

D It allows checking characters from both ends simultaneously, skipping unwanted characters, in a single pass with O(n) time.

💡 Hint

Think about how two pointers move towards each other and skip non-alphanumeric characters.

Two pointers start at the beginning and end of the string and move inward, skipping non-alphanumeric characters. This allows checking all relevant characters in one pass efficiently.

🚀 Application

expert

Final State of Pointers After Palindrome Check

Given the Rust code below checking palindrome with two pointers, what are the final values of left and right pointers after the function returns true for input "No lemon, no melon"?

DSA Rust

fn is_palindrome(s: &str) -> (bool, usize, usize) {
    let s = s.to_lowercase();
    let bytes = s.as_bytes();
    let (mut left, mut right) = (0, bytes.len() - 1);
    while left < right {
        if !bytes[left].is_ascii_alphanumeric() {
            left += 1;
            continue;
        }
        if !bytes[right].is_ascii_alphanumeric() {
            right -= 1;
            continue;
        }
        if bytes[left] != bytes[right] {
            return (false, left, right);
        }
        left += 1;
        right -= 1;
    }
    (true, left, right)
}

fn main() {
    let test_str = "No lemon, no melon";
    let (result, left, right) = is_palindrome(test_str);
    println!("{} {} {}", result, left, right);
}

A true 9 9

B true 7 7

C true 8 8

D true 9 6

💡 Hint

Trace the pointers moving inward and stopping when left >= right.

The pointers move inward skipping spaces and commas. They cross when left is 9 and right is 9, meaning the loop ends and the function returns true with these pointer values.

Practice

1. What is the main idea behind the two-pointer technique to check if a string is a palindrome?

easy

A. Reverse the string and compare it with the original string

B. Use two pointers starting from both ends and move towards the center comparing characters

C. Count the frequency of each character and check if all counts are even

D. Sort the characters and check if the sorted string equals the original

Solution

1. Step 1: Understand two-pointer approach

   The two-pointer technique uses one pointer at the start and one at the end of the string.

2. Step 2: Compare characters moving inward

   Both pointers move towards the center, comparing characters at each step to check equality.

3. Final Answer:

   Use two pointers starting from both ends and move towards the center comparing characters -> Option B

4. Quick Check:

   Two-pointer technique = Use two pointers starting from both ends and move towards the center comparing characters [OK]

Hint: Compare characters from both ends moving inward [OK]

Common Mistakes:

• Thinking reversing string is the two-pointer method
• Checking character counts instead of positions
• Sorting string changes order, not palindrome check

2. Which Rust code snippet correctly initializes two pointers for palindrome checking on a string s?

easy

A. let (mut left, mut right) = (0, s.len() - 1);

B. let (left, right) = (0, s.len());

C. let (mut left, mut right) = (1, s.len() - 1);

D. let (left, right) = (1, s.len());

Solution

1. Step 1: Identify pointer initialization for indices

   Left pointer starts at 0 (first char), right pointer at last index (length - 1).

2. Step 2: Check mutability and correct indices

   Both pointers must be mutable to move; right pointer must be s.len() - 1 to avoid out-of-bounds.

3. Final Answer:

   let (mut left, mut right) = (0, s.len() - 1); -> Option A

4. Quick Check:

   Correct pointer init = let (mut left, mut right) = (0, s.len() - 1); [OK]

Hint: Start left at 0 and right at length minus one [OK]

Common Mistakes:

• Using s.len() as right index causes out-of-bounds
• Not making pointers mutable
• Starting left pointer at 1 skips first character

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

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

fn main() {
    println!("{}", is_palindrome("racecar"));
    println!("{}", is_palindrome("hello"));
}

medium

A. false\nfalse

B. false\ntrue

C. true\nfalse

D. true\ntrue

Solution

1. Step 1: Check palindrome for "racecar"

   Characters match from both ends moving inward, so returns true.

2. Step 2: Check palindrome for "hello"

   Characters differ at first comparison ('h' vs 'o'), so returns false.

3. Final Answer:

   true\nfalse -> Option C

4. Quick Check:

   racecar = true, hello = false [OK]

Hint: Check first and last chars; mismatch means false [OK]

Common Mistakes:

• Assuming hello is palindrome
• Confusing output order
• Ignoring early return on mismatch

4. Identify the bug in this Rust function that checks palindrome and select the fix:

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

medium

A. Change right initialization to bytes.len() - 1

B. Change while condition to left <= right

C. Make left and right immutable

D. Use s.chars() instead of bytes

Solution

1. Step 1: Identify out-of-bounds error

   Right pointer is set to bytes.len(), which is out of valid index range (0 to len-1).

2. Step 2: Fix pointer initialization

   Set right to bytes.len() - 1 to point to last valid character index.

3. Final Answer:

   Change right initialization to bytes.len() - 1 -> Option A

4. Quick Check:

   Right pointer must be last index = Change right initialization to bytes.len() - 1 [OK]

Hint: Right pointer = length minus one to avoid out-of-bounds [OK]

Common Mistakes:

• Using length as index causes panic
• Changing while condition without fixing index
• Making pointers immutable prevents movement

5. Given the string s = "A man, a plan, a canal: Panama", which Rust code modification correctly checks if s is a palindrome ignoring non-alphanumeric characters and case using two pointers?

hard

A. Convert string to uppercase and compare characters including punctuation

B. Reverse the string and compare directly without filtering

C. Count characters ignoring case but include spaces and punctuation

D. Use two pointers skipping non-alphanumeric chars and compare lowercase characters

Solution

1. Step 1: Understand problem requirements

   We must ignore non-alphanumeric characters and case differences when checking palindrome.

2. Step 2: Apply two-pointer with skipping and case normalization

   Move pointers inward, skip chars that are not letters or digits, compare lowercase versions of characters.

3. Final Answer:

   Use two pointers skipping non-alphanumeric chars and compare lowercase characters -> Option D

4. Quick Check:

   Skip non-alphanumeric + lowercase compare = Use two pointers skipping non-alphanumeric chars and compare lowercase characters [OK]

Hint: Skip non-letters/digits and compare lowercase chars [OK]

Common Mistakes:

• Comparing with punctuation included
• Ignoring case differences
• Reversing string without filtering