Valid Palindrome Two Pointer in DSA C# - Execution Trace

Concept Flow - Valid Palindrome Two Pointer

Start: left=0, right=length-1

↓

Check if left < right?

No→End: Palindrome

Yes↓

Is s[left

Yes↓

Is s[right

Yes↓

Compare s[left

↓

left++, right--

↩Back to Check if left < right?

Two pointers move inward from both ends, skipping non-alphanumeric characters, comparing characters case-insensitively until pointers cross or mismatch.

Execution Sample

DSA C#

string s = "A man, a plan, a canal: Panama";
int left = 0, right = s.Length - 1;
while (left < right) {
  // skip non-alphanumeric
  // compare characters
  // move pointers
}
return true;

Check if the string is a palindrome ignoring cases and non-alphanumeric characters using two pointers.

Execution Table

Step	Operation	left	right	Characters Compared	Match?	Action	Visual State
1	Initialize pointers	0	29	-	-	Start	"A man, a plan, a canal: Panama"
2	Compare characters	0	29	'A' vs 'a'	Yes	left=1, right=28	"A man, a plan, a canal: Panama"
3	Skip non-alphanumeric at left	1	28	N/A	N/A	left=2	"A man, a plan, a canal: Panama"
4	Compare characters	2	28	'm' vs 'm'	Yes	left=3, right=27	"A man, a plan, a canal: Panama"
5	Compare characters	3	27	'a' vs 'a'	Yes	left=4, right=26	"A man, a plan, a canal: Panama"
6	Compare characters	4	26	'n' vs 'n'	Yes	left=5, right=25	"A man, a plan, a canal: Panama"
7	Skip non-alphanumeric at left	5	25	N/A	N/A	left=6	"A man, a plan, a canal: Panama"
8	Skip non-alphanumeric at left	6	25	N/A	N/A	left=7	"A man, a plan, a canal: Panama"
9	Compare characters	7	25	'a' vs 'a'	Yes	left=8, right=24	"A man, a plan, a canal: Panama"
10	Skip non-alphanumeric at left	8	24	N/A	N/A	left=9	"A man, a plan, a canal: Panama"
11	Compare characters	9	24	'p' vs 'P'	Yes	left=10, right=23	"A man, a plan, a canal: Panama"
12	Skip non-alphanumeric at right	10	23	N/A	N/A	right=22	"A man, a plan, a canal: Panama"
13	Skip non-alphanumeric at right	10	22	N/A	N/A	right=21	"A man, a plan, a canal: Panama"
14	Compare characters	10	21	'l' vs 'l'	Yes	left=11, right=20	"A man, a plan, a canal: Panama"
15	Compare characters	11	20	'a' vs 'a'	Yes	left=12, right=19	"A man, a plan, a canal: Panama"
16	Compare characters	12	19	'n' vs 'n'	Yes	left=13, right=18	"A man, a plan, a canal: Panama"
17	Skip non-alphanumeric at left	13	18	N/A	N/A	left=14	"A man, a plan, a canal: Panama"
18	Skip non-alphanumeric at left	14	18	N/A	N/A	left=15	"A man, a plan, a canal: Panama"
19	Compare characters	15	18	'a' vs 'a'	Yes	left=16, right=17	"A man, a plan, a canal: Panama"
20	Skip non-alphanumeric at left	16	17	N/A	N/A	left=17	"A man, a plan, a canal: Panama"
21	left >= right	17	17	-	-	End: Palindrome	"A man, a plan, a canal: Panama"

💡 All matching pairs found until pointers meet at left=17, right=17, confirming it's a palindrome

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 11	After Step 14	After Step 19
left	0	1	3	5	8	10	11	16
right	29	28	27	25	24	23	20	17

Key Moments - 3 Insights

Why do we skip characters that are not letters or numbers?

Because the palindrome check ignores spaces, punctuation, and symbols. See steps 3,7,8,10,12,13,17,18,20 in the execution_table where left or right pointers move past non-alphanumeric characters.

Why do we compare characters case-insensitively?

Because uppercase and lowercase letters are considered the same in palindrome check. For example, step 2 compares 'A' and 'a', and step 11 compares 'p' and 'P'; they match.

What happens when pointers meet or cross?

The function returns true, as shown in step 21 where left == right after all matches, confirming palindrome.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what are the values of left and right pointers after the action?

A left=1, right=28

B left=0, right=29

C left=2, right=27

D left=3, right=27

💡 Hint

Check the 'Action' column in execution_table row with Step=2

At which step does the algorithm conclude it's a palindrome?

A Step 19

B Step 21

C Step 14

D Step 11

💡 Hint

Look for 'End: Palindrome' in the 'Action' column of execution_table

If the input string had no non-alphanumeric characters, how would the pointer movement change?

A Pointers would move only after comparing characters

B Pointers would skip more characters

C Pointers would not move at all

D Pointers would move randomly

💡 Hint

Refer to the 'Operation' column in execution_table; skips only occur for non-alphanumeric characters

Concept Snapshot

Two pointers start at string ends
Skip non-alphanumeric characters
Compare characters ignoring case
If mismatch, return false
If pointers cross, return true
Efficient palindrome check

Full Transcript

This concept uses two pointers starting at the beginning and end of the string. Each pointer moves inward, skipping characters that are not letters or numbers. The characters at the pointers are compared without considering case differences. If all compared characters match, the string is a palindrome. If any pair does not match, the function returns false immediately. The process continues until the pointers cross, confirming the string is a palindrome.

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