Valid Palindrome Two Pointer in DSA C# - Time & Space Complexity

Time Complexity: Valid Palindrome Two Pointer

O(n)

Understanding Time Complexity

We want to know how the time needed to check if a string is a palindrome grows as the string gets longer.

Specifically, how many steps does the two-pointer method take as input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code checks if a string is a palindrome by moving two pointers from both ends toward the center, skipping non-alphanumeric characters.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves two pointers inward checking characters.
• How many times: At most, each character is visited once by either pointer, so up to n times where n is string length.

How Execution Grows With Input

As the string length grows, the number of steps grows roughly in a straight line with it.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: Doubling the input roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows directly in proportion to the string length.

Common Mistake

[X] Wrong: "Because there are two pointers, the time is doubled or squared."

[OK] Correct: Both pointers move inward and together visit each character only once, so total work is still proportional to n, not n squared.

Interview Connect

Understanding this linear time check is a great skill for interviews, showing you can analyze simple but efficient string algorithms clearly.

Self-Check

"What if we changed the code to check every character against every other character? How would the time complexity change?"

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