Palindrome Detection in DSA C# - Execution Trace

Concept Flow - Palindrome Detection

Start

↓

Input String

↓

Set left = 0, right = length-1

↓

Compare chars at left and right

↓

Return False

Yes↓

Move left++ and right--

↓

left < right?

No→Return True

↩Back to Compare chars

Check characters from both ends moving inward; if all pairs match, it's a palindrome.

Execution Sample

DSA C#

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

Checks if the string 'racecar' reads the same forwards and backwards.

Execution Table

Step	Operation	Left Index	Right Index	Chars Compared	Match?	Action	Visual State
1	Compare chars	0	6	'r' vs 'r'	Yes	left++, right--	'racecar'
2	Compare chars	1	5	'a' vs 'a'	Yes	left++, right--	'racecar'
3	Compare chars	2	4	'c' vs 'c'	Yes	left++, right--	'racecar'
4	Check condition	3	3	left < right?	No	Return True	'racecar'

💡 left (3) is not less than right (3), so all pairs matched; string is palindrome.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4 (End)
left	0	1	2	3	3
right	6	5	4	3	3
result	undefined	undefined	undefined	undefined	true

Key Moments - 3 Insights

Why do we stop comparing when left is not less than right?

Because when left >= right, all character pairs have been checked. See execution_table step 4 where left=3 and right=3, so loop ends and palindrome is confirmed.

What if characters at left and right don't match?

We immediately return false, ending the check early. This is shown in the 'Match?' column in execution_table; if 'No', action is to return false.

Why do we compare s[left] and s[right] instead of the whole string?

Comparing pairs from ends inward is efficient and enough to confirm palindrome. The execution_table shows only pairs compared, not the whole string each time.

Visual Quiz - 3 Questions

Look at the execution_table, what characters are compared at step 3?

A 'a' vs 'a'

B 'c' vs 'c'

C 'e' vs 'e'

D 'r' vs 'r'

💡 Hint

Check the 'Chars Compared' column in execution_table row for step 3.

At which step does the loop stop because left is no longer less than right?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'Check condition' operation and 'left < right?' result in execution_table.

If the string was 'hello', what would happen at the first comparison step?

A Characters match, continue checking

B Characters don't match, return false immediately

C Loop runs until left >= right

D Return true immediately

💡 Hint

Recall from key_moments what happens when characters don't match at any step.

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters at left and right
- If mismatch, return false
- Move pointers inward (left++, right--)
- Stop when left >= right, return true
- Efficient check without reversing string

Full Transcript

This visualization shows how palindrome detection works by comparing characters from the start and end of a string moving inward. We start with two pointers: left at index 0 and right at the last index. At each step, we compare the characters at these pointers. If they match, we move the pointers closer to the center. If they don't match, we return false immediately. When the left pointer is no longer less than the right pointer, it means all pairs matched and the string is a palindrome. The example uses the string 'racecar' and confirms it is a palindrome after three successful comparisons.

Practice

1. What is a palindrome in the context of strings?

easy

A. A string that contains only vowels

B. A string that reads the same forwards and backwards

C. A string with all unique characters

D. A string that is empty

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same forwards and backwards, ignoring spaces and punctuation.

2. Step 2: Apply definition to options

   A string that reads the same forwards and backwards matches this definition exactly, while others describe different string properties.

3. Final Answer:

   A string that reads the same forwards and backwards -> Option B

4. Quick Check:

   Palindrome = Same forwards and backwards [OK]

Hint: Check if string reversed equals original [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking palindrome means only vowels
• Assuming empty string is always palindrome

2. Which of the following C# code snippets correctly checks if a string s is a palindrome?

easy

A. return s.Length == 0;

B. return s == s.ToUpper();

C. return s == new string(s.Reverse().ToArray());

D. return s[0] == s[s.Length];

Solution

1. Step 1: Understand palindrome check logic

   To check palindrome, compare string with its reversed version.

2. Step 2: Analyze each option

   return s == new string(s.Reverse().ToArray()); reverses string and compares correctly. return s == s.ToUpper(); compares uppercase, not palindrome. return s.Length == 0; checks empty string only. return s[0] == s[s.Length]; accesses invalid index (out of range).

3. Final Answer:

   return s == new string(s.Reverse().ToArray()); -> Option C

4. Quick Check:

   Reverse and compare = return s == new string(s.Reverse().ToArray()); [OK]

Hint: Reverse string and compare to original [OK]

Common Mistakes:

• Using wrong index causing out of range error
• Comparing uppercase instead of reversed string
• Checking only empty string

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

string s = "level";
bool isPalindrome = s == new string(s.Reverse().ToArray());
Console.WriteLine(isPalindrome);

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Reverse the string "level"

   Reversed string is "level", same as original.

2. Step 2: Compare original and reversed strings

   Since both are equal, isPalindrome is true, so Console.WriteLine prints True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   "level" reversed = "level" [OK]

Hint: Check if reversed string equals original [OK]

Common Mistakes:

• Assuming output is False for palindromes
• Confusing compilation error due to Reverse()
• Thinking runtime exception occurs

4. Identify the error in this palindrome check code and select the fix:

string s = "test";
bool isPalindrome = true;
for (int i = 0; i <= s.Length / 2; i++)
{
    if (s[i] != s[s.Length - i])
    {
        isPalindrome = false;
        break;
    }
}
Console.WriteLine(isPalindrome);

medium

A. Remove the break statement

B. Change loop condition to i < s.Length

C. Initialize isPalindrome to false

D. Change s.Length - i to s.Length - i - 1

Solution

1. Step 1: Identify index error in character comparison

   String indices go from 0 to s.Length - 1, so s[s.Length - i] is out of range when i=0.

2. Step 2: Fix index to s.Length - i - 1

   This correctly accesses the mirrored character from the end.

3. Final Answer:

   Change s.Length - i to s.Length - i - 1 -> Option D

4. Quick Check:

   Correct index fixes out of range error [OK]

Hint: Remember last index is length minus one [OK]

Common Mistakes:

• Using s.Length - i instead of s.Length - i - 1
• Looping beyond half the string length
• Removing break causing unnecessary checks

5. You want to detect if a string is a palindrome ignoring case and spaces. Which code snippet correctly implements this in C#?

hard

A. string clean = new string(s.Where(char.IsLetterOrDigit).ToArray()).ToLower();
bool isPal = clean == new string(clean.Reverse().ToArray());

B. string clean = s.Replace(" ", "");
bool isPal = clean == clean.ToUpper();

C. bool isPal = s == new string(s.Reverse().ToArray());

D. bool isPal = s.ToLower() == s.ToUpper();

Solution

1. Step 1: Clean string by removing non-letter/digit and convert to lowercase

   string clean = new string(s.Where(char.IsLetterOrDigit).ToArray()).ToLower(); bool isPal = clean == new string(clean.Reverse().ToArray()); uses Where with char.IsLetterOrDigit and ToLower to normalize string.

2. Step 2: Reverse cleaned string and compare

   string clean = new string(s.Where(char.IsLetterOrDigit).ToArray()).ToLower(); bool isPal = clean == new string(clean.Reverse().ToArray()); reverses cleaned string and compares correctly for palindrome ignoring case and spaces.

3. Final Answer:

   string clean = new string(s.Where(char.IsLetterOrDigit).ToArray()).ToLower(); bool isPal = clean == new string(clean.Reverse().ToArray()); -> Option A

4. Quick Check:

   Normalize then reverse and compare = string clean = new string(s.Where(char.IsLetterOrDigit).ToArray()).ToLower(); bool isPal = clean == new string(clean.Reverse().ToArray()); [OK]

Hint: Remove spaces and lowercase before checking palindrome [OK]

Common Mistakes:

• Not removing spaces or punctuation
• Comparing original string without normalization
• Using uppercase comparison incorrectly