Valid Palindrome Two Pointer in DSA C#

Mental Model

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

Analogy: Imagine two friends starting at opposite ends of a line of people, checking if each pair of friends looks the same until they meet in the middle.

h -> e -> l -> l -> o
↑                 ↑
left             right

Dry Run Walkthrough

Input: string: "A man, a plan, a canal: Panama"

Goal: Determine if the string is a palindrome ignoring spaces, punctuation, and case

Step 1: Initialize left pointer at start and right pointer at end

A ->   -> m -> a -> n -> , ->   -> a ->   -> p -> l -> a -> n -> , ->   -> a ->   -> c -> a -> n -> a -> l -> : ->   -> P -> a -> n -> a -> m -> a
↑                                                                                                               ↑

Why: We need to compare characters from both ends moving inward

Step 2: Skip non-alphanumeric characters at left and right pointers

A -> m -> a -> n -> a -> p -> l -> a -> n -> a -> c -> a -> n -> a -> l -> P -> a -> n -> a -> m -> a
↑                                                                                   ↑

Why: Ignore spaces and punctuation to focus on letters and numbers

Step 3: Compare characters at left and right pointers ignoring case: 'a' vs 'a' match, move inward

m -> a -> n -> a -> p -> l -> a -> n -> a -> c -> a -> n -> a -> l -> P -> a -> n -> a -> m
  ↑                                                                             ↑

Why: Matching characters confirm palindrome property so far

Step 4: Continue comparing pairs: 'm' vs 'm', 'a' vs 'a', 'n' vs 'n', moving pointers inward

a -> p -> l -> a -> n -> a -> c -> a -> n -> a -> l -> P -> a -> n -> a
    ↑                                                               ↑

Why: Keep verifying matching pairs until pointers meet or cross

Step 5: Pointers cross without mismatch, confirming palindrome

Pointers crossed, all compared characters matched

Why: No mismatches found, string is a valid palindrome

Result:

Pointers crossed, string is a valid palindrome

Annotated Code

DSA C#

using System;

public class Solution {
    public static bool IsPalindrome(string s) {
        int left = 0;
        int right = s.Length - 1;

        while (left < right) {
            // Skip non-alphanumeric from left
            while (left < right && !Char.IsLetterOrDigit(s[left])) {
                left++;
            }
            // Skip non-alphanumeric from right
            while (left < right && !Char.IsLetterOrDigit(s[right])) {
                right--;
            }
            // Compare characters ignoring case
            if (Char.ToLower(s[left]) != Char.ToLower(s[right])) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void Main() {
        string input = "A man, a plan, a canal: Panama";
        bool result = IsPalindrome(input);
        Console.WriteLine(result ? "Valid palindrome" : "Not a palindrome");
    }
}

while (left < right && !Char.IsLetterOrDigit(s[left])) { left++; }

Skip non-alphanumeric characters from the left pointer

while (left < right && !Char.IsLetterOrDigit(s[right])) { right--; }

Skip non-alphanumeric characters from the right pointer

if (Char.ToLower(s[left]) != Char.ToLower(s[right])) { return false; }

Compare characters ignoring case; if mismatch, string is not palindrome

left++; right--;

Move pointers inward to compare next pair

Output

Valid palindrome

Complexity Analysis

Time: O(n) because we scan the string once with two pointers moving inward

Space: O(1) because we use only fixed extra space for pointers and comparisons

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

Edge Cases

Empty string

Returns true because empty string reads the same forwards and backwards

DSA C#

while (left < right && !Char.IsLetterOrDigit(s[left])) { left++; }

String with only non-alphanumeric characters

Returns true because ignoring non-alphanumeric leaves empty string

DSA C#

while (left < right && !Char.IsLetterOrDigit(s[left])) { left++; }

Single character string

Returns true because single character is palindrome

DSA C#

while (left < right && !Char.IsLetterOrDigit(s[left])) { left++; }

When to Use This Pattern

When you need to check if a string reads the same forwards and backwards ignoring spaces and punctuation, use the two-pointer palindrome pattern for efficient comparison.

Common Mistakes

Mistake: Not skipping non-alphanumeric characters before comparing
Fix: Add loops to move pointers past non-alphanumeric characters before each comparison

Mistake: Comparing characters without ignoring case
Fix: Convert characters to lower case before comparing

Summary

Checks if a string is a palindrome by comparing characters from both ends moving inward.

Use when verifying palindrome strings ignoring spaces, punctuation, and case.

The key insight is to skip irrelevant characters and compare pairs moving inward until pointers meet or cross.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the two-pointer approach

   Two pointers start at the beginning and end of the string and move inward.

2. Step 2: Compare characters at pointers

   If characters are equal, move pointers closer; if not, string is not palindrome.

3. Final Answer:

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

4. Quick Check:

   Two-pointer technique = Compare ends inward [OK]

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

Common Mistakes:

• Reversing string instead of using pointers
• Checking only half the string incorrectly
• Ignoring case or non-alphanumeric characters

2. Which of the following C# code snippets correctly initializes two pointers for palindrome checking on string s?

easy

A. int left = 0, right = s.Length - 1;

B. int left = 1, right = s.Length;

C. int left = 0, right = s.Length;

D. int left = 1, right = s.Length - 1;

Solution

1. Step 1: Identify valid pointer initialization

   Left pointer starts at 0 (first char), right pointer at s.Length - 1 (last char).

2. Step 2: Check each option

   int left = 0, right = s.Length - 1; correctly sets left=0 and right=s.Length-1; others are off by one.

3. Final Answer:

   int left = 0, right = s.Length - 1; -> Option A

4. Quick Check:

   Pointers start at 0 and last index [OK]

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

Common Mistakes:

• Setting right pointer to s.Length (out of range)
• Starting left pointer at 1 instead of 0
• Confusing length with last index

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

string s = "A man, a plan, a canal: Panama";
bool IsPalindrome(string str) {
    int left = 0, right = str.Length - 1;
    while (left < right) {
        if (!char.IsLetterOrDigit(str[left])) { left++; continue; }
        if (!char.IsLetterOrDigit(str[right])) { right--; continue; }
        if (char.ToLower(str[left]) != char.ToLower(str[right])) return false;
        left++; right--;
    }
    return true;
}
Console.WriteLine(IsPalindrome(s));

medium

A. Runtime exception

B. True

C. Compilation error

D. False

Solution

1. Step 1: Understand the code logic

   The code skips non-alphanumeric characters and compares letters ignoring case.

2. Step 2: Analyze the input string

   "A man, a plan, a canal: Panama" is a famous palindrome ignoring spaces and punctuation.

3. Final Answer:

   True -> Option B

4. Quick Check:

   Ignoring punctuation and case, string is palindrome [OK]

Hint: Ignore non-letters and compare lowercase chars [OK]

Common Mistakes:

• Not skipping non-alphanumeric characters
• Comparing characters without case normalization
• Assuming spaces affect palindrome check

4. Identify the bug in the following palindrome check code and select the fix:

bool IsPalindrome(string s) {
    int left = 0, right = s.Length - 1;
    while (left <= right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

medium

A. Change while condition to left < right

B. Skip non-alphanumeric characters before comparing

C. All of the above

D. Add case-insensitive comparison using char.ToLower

Solution

1. Step 1: Check loop condition correctness

   Using <= causes unnecessary comparison when left == right; < is better.

2. Step 2: Consider case and character filtering

   Comparisons should ignore case and skip non-alphanumeric chars for valid palindrome check.

3. Step 3: Combine fixes

   All suggested fixes improve correctness and handle common palindrome cases.

4. Final Answer:

   All of the above -> Option C

5. Quick Check:

   Loop, case, and filtering fixes needed [OK]

Hint: Check loop, case, and skip non-letters [OK]

Common Mistakes:

• Using <= instead of < in loop
• Ignoring case differences
• Not skipping punctuation or spaces

5. Given the string "No lemon, no melon", which modification to the two-pointer palindrome check is necessary to correctly identify it as a palindrome?

hard

A. Convert characters to lowercase and skip non-alphanumeric characters during comparison

B. Only convert characters to lowercase without skipping any characters

C. Skip spaces only, but compare punctuation as is

D. Reverse the string and compare directly without any preprocessing

Solution

1. Step 1: Analyze the string content

   "No lemon, no melon" contains spaces and punctuation that should be ignored.

2. Step 2: Determine necessary preprocessing

   Lowercase conversion and skipping all non-alphanumeric characters ensures correct palindrome check.

3. Final Answer:

   Convert characters to lowercase and skip non-alphanumeric characters during comparison -> Option A

4. Quick Check:

   Lowercase + skip non-alphanumeric = correct palindrome check [OK]

Hint: Lowercase and skip all non-letters/digits [OK]

Common Mistakes:

• Skipping only spaces but not punctuation
• Ignoring case differences
• Comparing raw strings without preprocessing