Check a string is a palindrome in O(n), ignoring case and non-letters
Implement IsPalindrome(s) that returns true when s reads the same forwards and backwards, ignoring case and any character that is not a letter. Requirements: O(n) time and O(1) extra space — scan with two pointers from both ends, do not build a cleaned copy of the string. "A man, a Plan!" is NOT a palindrome but "Madam" and "" are.
public static bool IsPalindrome(string s)
{
// your code here
return false;
}Write the implementation.
Two pointers l = 0 and r = s.Length - 1 moving inward. Skip any character where char.IsLetter is false on either side, then compare with char.ToLower; mismatch returns false. Meeting in the middle returns true. O(n) time, O(1) extra space.
- ✗Building a cleaned/reversed copy, which costs O(n) extra space instead of O(1)
- ✗Comparing characters without normalizing case via
char.ToLower - ✗Forgetting to skip non-letters on BOTH sides before each comparison
- →How would you also treat digits as significant characters?
- →Why does skipping non-letters inside the loop keep it O(n) overall?
Task
Check whether the string reads the same in both directions, ignoring case and non-letters.
public static bool IsPalindrome(string s)
{
int l = 0, r = s.Length - 1;
while (l < r)
{
if (!char.IsLetter(s[l])) { l++; continue; } // skip on the left
if (!char.IsLetter(s[r])) { r--; continue; } // skip on the right
if (char.ToLower(s[l]) != char.ToLower(s[r]))
return false;
l++;
r--;
}
return true;
}How it works
Two pointers start at the ends and converge toward the middle. Before comparing a pair of characters, each pointer is advanced past anything that is not a letter (char.IsLetter), so punctuation and spaces never affect the result.
The comparison lowercases both characters (char.ToLower), so case is ignored. Any mismatch returns false immediately. If the pointers meet, the string is a palindrome.
Each character is visited at most once, giving O(n) time and O(1) space — no cleaned copy of the string is allocated. The empty string runs the loop zero times and correctly returns true.
