You are given a string s. Return true if it is a palindrome, and false if it is not. A palindrome reads the same forwards and backwards, like "level" or "noon". For this problem, two extra rules apply.
Ignore upper and lower case. A and a count as the same letter.
Ignore every character that is not a letter or a digit. Spaces, commas, colons and so on are simply skipped.
s = "A man, a plan, a canal: Panama" → trues = "race a car" → falses = " " → true
The first example becomes "amanaplanacanalpanama" once the junk is removed and everything is lowercase, and that reads the same both ways. The second becomes "raceacar", which reversed is "racaecar", so it is not a palindrome. The third has no letters or digits left at all. An empty string reads the same both ways, so the answer is true.
A string is a palindrome when its first character matches its last, its second matches its second-to-last, and so on, all the way to the middle. So the real question is: "do the characters match in pairs, working inwards from both ends?" The only twist is that some characters do not count and must be skipped.
Build a clean copy of the string, with only lowercase letters and digits. Then compare the copy with its reverse.
python
def isPalindrome(s): cleaned = ''.join(c.lower() for c in s if c.isalnum()) return cleaned == cleaned[::-1]
c.isalnum() is True when c is a letter or a digit. cleaned[::-1] is Python's way of writing "the string reversed". This is short, correct, and a fine first answer.
It is already O(n) time, so speed is not the problem. The waste is memory: it builds two new strings, the cleaned copy and its reverse, each as long as the input. If the string were a gigabyte, you would need two more gigabytes.
class Solution: def isPalindrome(self, s: str) -> bool: l, r = 0, len(s) - 1 # (1) while l < r: # (2) while l < r and not s[l].isalnum(): # (3) l += 1 while l < r and not s[r].isalnum(): # (4) r -= 1 if s[l].lower() != s[r].lower(): # (5) return False l += 1 # (6) r -= 1 return True # (7)
ts
function isPalindrome(s: string): boolean { const ok = (c: string) => /[a-z0-9]/i.test(c); // letter or digit? let l = 0, r = s.length - 1; // (1) while (l < r) { // (2) while (l < r && !ok(s[l])) l++; // (3) while (l < r && !ok(s[r])) r--; // (4) if (s[l].toLowerCase() !== s[r].toLowerCase()) { // (5) return false; } l++; // (6) r--; } return true; // (7)}
(1) Place the two pointers.l starts at the first position, 0. r starts at the last position, len(s) - 1. We subtract 1 because positions start counting at 0, so a string of length 5 has positions 0 to 4.
(2) Keep going while the pointers have not met. When l and r meet or cross, every pair has been checked. If the string has an odd number of real characters, the middle one is left alone. That is fine, because a single character always matches itself.
(3) Skip junk on the left. While the character at l is not a letter or digit, move l one step right. TypeScript has no isalnum, so we write a tiny helper, ok, using a regular expression. A regular expression is a short pattern for matching text. /[a-z0-9]/i means "one character from a to z or 0 to 9", and the i at the end means "ignore case".
(4) Skip junk on the right, moving r one step left.
The check l < r inside lines (3) and (4) is easy to forget, and it matters. Take the string ",,,", which is all junk. Without the check, line (3) would keep moving l right, past the end of the string, and the program would crash. With the check, l stops when it reaches r. The outer loop then ends, and we return true.
(5) Compare, ignoring case..lower() turns both characters into lowercase, so A and a compare as equal. If they still differ, the string is not a palindrome, and we return false immediately.
(6) Move both pointers inward. This pair matched, so we step past both characters to the next pair.
(7) Every pair matched. The string is a palindrome.
Time.l only ever moves right, and r only ever moves left. Between them they can cross the string at most once, so together they take at most n steps. Each step does a constant amount of work. So the time is O(n).
The loops inside the loop do not make this O(n^2). They do not restart from the beginning. They just move the same two pointers further along, and the pointers never move back.
Space. We only keep two numbers, l and r. That does not grow with the string, so the extra memory is O(1). This is the whole reason to prefer this version over the cleaned-copy version.
Valid Palindrome II. You may delete at most one character. When the two pointers disagree, try skipping the left character, and also try skipping the right one. If either of the two remaining stretches is a palindrome, the answer is true.
Longest Palindromic Substring and Palindromic Substrings. Instead of moving inward from the ends, you start from each possible middle and move outward. See 4.23.5.
Reverse a string in place. The same two pointers, swapping instead of comparing.
The general lesson: when a question compares the two ends of a sequence, put one pointer at each end and walk them toward each other.
"Can you do it without extra memory?" They want the pointer version, and the reason: two pointers skip junk where it stands, so no copies are needed.
"What happens on a string of only punctuation?" They are checking the l < r guard in the inner loops. Without it, the pointer runs off the end.
"Why don't the inner loops make it O(n^2)?" Because neither pointer ever moves backwards. They take at most n steps between them, in total.
"What about Unicode letters, like é?" Python's isalnum already accepts them. The TypeScript pattern [a-z0-9] does not, so you would use /[\p{L}\p{N}]/u, which means "any letter or any digit in any language".
One thing to volunteer: offer the two-line cleaned-copy version first, because it is clear. Then offer the pointer version when memory comes up. Showing both, and the trade between them, is better than jumping to the clever one.
Next:4.5.2 Two Sum II. The same two pointers, but now we must prove which pointer should move.