Valid Palindrome Two Pointer in DSA Rust

Mental Model

Check if a word reads the same forwards and backwards by comparing letters from both ends moving towards the center.

Analogy: Like two friends starting at opposite ends of a row of books, checking if the titles match as they move closer to the middle.

s = "r a c e c a r"
left ↑                 right ↑

Dry Run Walkthrough

Input: string: "racecar"

Goal: Determine if the string is a palindrome by comparing characters from both ends moving inward.

Step 1: Compare characters at left=0 and right=6 ('r' and 'r')

r a c e c a r
↑                 ↑

Why: Start comparing outer characters to check if they match

Step 2: Move left to 1 and right to 5, compare 'a' and 'a'

r a c e c a r
  ↑             ↑

Why: Characters matched, move inward to continue checking

Step 3: Move left to 2 and right to 4, compare 'c' and 'c'

r a c e c a r
    ↑         ↑

Why: Continue inward comparison as characters still match

Step 4: Move left to 3 and right to 3

r a c e c a r
      ↑     ↑

Why: Pointers meet in the middle, loop exits (left not < right), no need to compare center

Step 5: Since all pairs matched, conclude string is palindrome

r a c e c a r
        ↑

Why: All characters matched symmetrically

Result:

r a c e c a r
Palindrome: true

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 found, not palindrome
        }
        left += 1; // move left pointer inward
        right = right.saturating_sub(1); // move right pointer inward
    }
    true // all matched, is palindrome
}

fn main() {
    let input = "racecar";
    let result = is_palindrome(input);
    println!("{}\nPalindrome: {}", input, result);
}

while left < right {

loop until pointers meet or cross

if bytes[left] != bytes[right] {

check if characters at pointers differ

return false; // mismatch found, not palindrome

stop early if mismatch

left += 1; // move left pointer inward

advance left pointer to next character

right = right.saturating_sub(1); // move right pointer inward

move right pointer inward safely

Output

racecar

Palindrome: true

Complexity Analysis

Time: O(n) because we compare pairs of characters from both ends once until the middle

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to reversing the string and comparing, this uses less space and stops early on mismatch

Edge Cases

empty string

returns true because empty string reads the same forwards and backwards

DSA Rust

let mut right = bytes.len().saturating_sub(1);

single character string

returns true because a single character is always a palindrome

DSA Rust

while left < right {

string with mismatched characters

returns false as soon as a mismatch is found

DSA Rust

if bytes[left] != bytes[right] {

When to Use This Pattern

When you need to check if a sequence reads the same forwards and backwards, use two pointers from both ends moving inward to compare characters efficiently.

Common Mistakes

Mistake: Not stopping the loop when pointers cross, causing unnecessary comparisons or errors
Fix: Use 'while left < right' condition to stop when pointers meet or cross

Mistake: Not handling empty strings correctly, causing underflow when subtracting 1 from length
Fix: Use saturating_sub(1) to safely handle empty strings

Summary

Checks if a string reads the same forwards and backwards by comparing characters from both ends.

Use when you want to verify palindrome property efficiently without extra space.

The key insight is comparing pairs of characters from the outside moving inward until pointers meet.

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