Palindrome Detection in DSA C#

Mental Model

A palindrome reads the same forwards and backwards. We check if the first half matches the reversed second half.

Analogy: Like reading a word on a mirror: if the reflection looks the same as the original, it's a palindrome.

head -> [p] -> [a] -> [l] -> [i] -> [n] -> [d] -> [r] -> [o] -> [m] -> [e] -> null
↑start                                         ↑end

Dry Run Walkthrough

Input: string: "racecar"

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

Step 1: Set two pointers: start at 'r' (index 0), end at 'r' (index 6)

r (start) -> a -> c -> e -> c -> a -> r (end)

Why: We compare characters from both ends moving inward

Step 2: Compare characters at start and end: 'r' == 'r', move inward

r -> a (start) -> c -> e -> c -> a (end) -> r

Why: Matching characters mean palindrome so far

Step 3: Compare characters at start and end: 'a' == 'a', move inward

r -> a -> c (start) -> e -> c (end) -> a -> r

Why: Still matching, continue checking

Step 4: Compare characters at start and end: 'c' == 'c', move inward

r -> a -> c -> e (start and end) -> c -> a -> r

Why: Middle character reached, no mismatch found

Result:

r -> a -> c -> e -> c -> a -> r -> null
Palindrome detected: true

Annotated Code

DSA C#

using System;

class PalindromeChecker
{
    public static bool IsPalindrome(string s)
    {
        int start = 0;
        int end = s.Length - 1;

        while (start < end)
        {
            if (s[start] != s[end])
            {
                return false; // mismatch found, not palindrome
            }
            start++; // move start pointer inward
            end--;   // move end pointer inward
        }
        return true; // all matched, palindrome
    }

    static void Main()
    {
        string input = "racecar";
        bool result = IsPalindrome(input);
        Console.WriteLine(string.Join(" -> ", input.ToCharArray()) + " -> null");
        Console.WriteLine("Palindrome detected: " + result.ToString().ToLower());
    }
}

while (start < end)

loop to compare characters from both ends moving inward

if (s[start] != s[end])

check for mismatch, if found return false immediately

start++; end--;

advance pointers inward to next characters

return true;

all characters matched, confirm palindrome

Output

r -> a -> c -> e -> c -> a -> r -> null

Palindrome detected: true

Complexity Analysis

Time: O(n) because we compare characters from both ends up to the middle once

Space: O(1) because we use only two pointers and no extra storage

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 since empty string reads same forwards and backwards

DSA C#

while (start < end)

single character string

returns true because one character is always palindrome

DSA C#

while (start < end)

string with mismatch early

returns false immediately when first mismatch found

DSA C#

if (s[start] != s[end])

When to Use This Pattern

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

Common Mistakes

Mistake: Comparing characters but forgetting to move pointers inward, causing infinite loop
Fix: Increment start and decrement end pointers inside the loop after successful comparison

Summary

Checks if a string reads the same forwards and backwards.

Use when you want to verify palindrome property efficiently.

The key insight is comparing characters from both ends moving inward until they meet.

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