Palindrome Detection in DSA Rust

Mental Model

A palindrome reads the same forwards and backwards. We check characters from both ends moving towards the center.

Analogy: Like checking if a word looks the same in a mirror placed at its center.

start: [p] -> [a] -> [l] -> [i] -> [n] -> [d] -> [r] -> [o] -> [m] -> [e]
indexes:  0       1       2       3       4       5       6       7       8       9

Dry Run Walkthrough

Input: string: "radar"

Goal: Check if the string reads the same forwards and backwards

Step 1: Compare characters at start=0 and end=4 ('r' and 'r')

"radar"

Why: Characters match, so continue checking inside

Step 2: Move start to 1 and end to 3, compare ('a' and 'a')

"radar"

Why: Characters still match, continue

Step 3: Move start to 2 and end to 2, compare ('d' and 'd')

"radar"

Why: Middle character reached, all pairs matched

Result:

"radar" is a palindrome

Annotated Code

DSA Rust

fn is_palindrome(s: &str) -> bool {
    let bytes = s.as_bytes();
    let mut start = 0;
    let mut end = bytes.len().saturating_sub(1);
    while start < end {
        if bytes[start] != bytes[end] {
            return false; // mismatch found, not palindrome
        }
        start += 1; // move start forward
        end = end.saturating_sub(1); // move end backward
    }
    true // all matched, is palindrome
}

fn main() {
    let test_str = "radar";
    if is_palindrome(test_str) {
        println!("{} is a palindrome", test_str);
    } else {
        println!("{} is not a palindrome", test_str);
    }
}

while start < end {

loop to compare characters from both ends moving inward

if bytes[start] != bytes[end] {

check if characters at current pointers differ

return false; // mismatch found, not palindrome

stop early if mismatch found

start += 1; // move start forward

advance start pointer towards center

end = end.saturating_sub(1); // move end backward

move end pointer towards center safely

true // all matched, is palindrome

if loop completes, string is palindrome

Output

radar is a palindrome

Complexity Analysis

Time: O(n) because we compare pairs of characters moving inward once

Space: O(1) because we use only fixed extra variables for pointers

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

Edge Cases

empty string

returns true because empty string reads same forwards and backwards

DSA Rust

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

single character string

returns true because single character is palindrome

DSA Rust

while start < end {

string with mismatched characters

returns false immediately when mismatch found

DSA Rust

if bytes[start] != bytes[end] {

When to Use This Pattern

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

Common Mistakes

Mistake: Not stopping early on mismatch and checking entire string unnecessarily
Fix: Return false immediately when a mismatch is found inside the loop

Mistake: Using string reversal which uses extra space and time
Fix: Use two-pointer approach to compare characters in place

Summary

Checks if a string reads the same forwards and backwards.

Use when you want to verify palindrome property efficiently.

Compare characters from both ends moving inward, stop early on mismatch.

Practice

1. What does a palindrome string mean in simple terms?

easy

A. It has all unique characters

B. It contains only vowels

C. It is always an even length string

D. It reads the same forwards and backwards

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same from left to right and right to left.

2. Step 2: Check options against definition

   Only It reads the same forwards and backwards matches this meaning exactly.

3. Final Answer:

   It reads the same forwards and backwards -> Option D

4. Quick Check:

   Palindrome = Same forwards and backwards [OK]

Hint: Palindrome means mirror reading same both ways [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking palindrome must be even length
• Assuming palindrome only has vowels

2. Which Rust code snippet correctly checks if a string s is a palindrome?

easy

A. s.reverse() == s

B. s.chars().eq(s.chars().rev())

C. s == s.reverse()

D. s.chars().all(|c| c == s.chars().next().unwrap())

Solution

1. Step 1: Understand Rust string palindrome check

   To check palindrome, compare characters iterator with its reverse iterator.

2. Step 2: Analyze options

   s.chars().eq(s.chars().rev()) uses chars().eq(chars().rev()) which correctly compares forward and backward characters. Options A and C use invalid methods or wrong comparisons. s.chars().all(|c| c == s.chars().next().unwrap()) checks if all characters are same, not palindrome.

3. Final Answer:

   s.chars().eq(s.chars().rev()) -> Option B

4. Quick Check:

   Compare chars iterator with reversed iterator [OK]

Hint: Use chars().eq(chars().rev()) to check palindrome [OK]

Common Mistakes:

• Using reverse() method on &str which does not exist
• Comparing string with reversed string incorrectly
• Checking all chars equal instead of palindrome

3. What is the output of this Rust code?

let s = "racecar";
let result = s.chars().eq(s.chars().rev());
println!("{}", result);

medium

A. true

B. Runtime panic

C. Compilation error

D. false

Solution

1. Step 1: Analyze the string and palindrome check

   The string "racecar" reads the same forwards and backwards, so it is a palindrome.

2. Step 2: Understand the code output

   The code compares characters forward and backward and returns true for palindrome strings. So, it prints true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   "racecar" palindrome check = true [OK]

Hint: Check if string equals its reverse chars [OK]

Common Mistakes:

• Assuming palindrome check returns false for odd length
• Thinking code causes compile or runtime error
• Confusing output with string itself

4. Identify the error in this Rust palindrome check code:

fn is_palindrome(s: &str) -> bool {
    s == s.chars().rev().collect::<String>()
}

medium

A. Cannot compare &str with String directly

B. Missing semicolon after collect

C. chars().rev() does not exist

D. Function return type should be String

Solution

1. Step 1: Understand types in comparison

   The left side is &str, right side is String from collect(). Direct comparison between &str and String is not allowed.

2. Step 2: Fix type mismatch

   Convert left side to String or right side to &str for comparison. For example, use s.to_string() == s.chars().rev().collect::<String>().

3. Final Answer:

   Cannot compare &str with String directly -> Option A

4. Quick Check:

   Type mismatch in comparison causes error [OK]

Hint: Compare same types: &str vs &str or String vs String [OK]

Common Mistakes:

• Ignoring type mismatch error
• Assuming collect needs semicolon inside expression
• Thinking chars().rev() is invalid method

5. You want to detect palindromes ignoring case and spaces in Rust. Which code snippet correctly implements this?

hard

A. let is_pal = s.chars().all(|c| c.is_alphanumeric());

B. let lower = s.to_lowercase();
let is_pal = lower == lower.reverse();

C. let filtered: String = s.chars().filter(|c| !c.is_whitespace()).collect();
let lower = filtered.to_lowercase();
let is_pal = lower.chars().eq(lower.chars().rev());

D. let filtered: String = s.chars().filter(|c| c.is_whitespace()).collect();
let is_pal = filtered == filtered.chars().rev().collect::<String>();

Solution

1. Step 1: Remove spaces and convert to lowercase

   let filtered: String = s.chars().filter(|c| !c.is_whitespace()).collect(); let lower = filtered.to_lowercase(); let is_pal = lower.chars().eq(lower.chars().rev()); filters out whitespace, collects characters, then converts to lowercase string.

2. Step 2: Check palindrome on cleaned string

   It compares characters forward and backward correctly on the cleaned lowercase string.

3. Final Answer:

   let filtered: String = s.chars().filter(|c| !c.is_whitespace()).collect(); let lower = filtered.to_lowercase(); let is_pal = lower.chars().eq(lower.chars().rev()); -> Option C

4. Quick Check:

   Filter spaces + lowercase + compare reversed chars [OK]

Hint: Clean string first: remove spaces, lowercase, then check palindrome [OK]

Common Mistakes:

• Using reverse() method which does not exist
• Filtering only whitespace but not converting case
• Checking all chars alphanumeric instead of palindrome