Skip to main content
DSA patterns

Valid Palindrome

easyTwo pointers Must-doTCSInfosysCognizant

Problem statement

Given a string s, check whether it reads the same forwards and backwards once you ignore case and drop everything that isn't a letter or digit — punctuation, spaces, colons, all of it. Return true if it does.

Think of it as sanity-checking a value that should be symmetric, like a checksum or a palindrome-shaped identifier, while ignoring formatting characters someone added for readability.

Examples

Example 1

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: Stripping punctuation and spaces and lowercasing everything gives "amanaplanacanalpanama", which reads the same both ways.

Example 2

Input: s = "race a car"

Output: false

Explanation: Cleaned up, this is "raceacar" — the second letter from the start is "a" but the second from the end is "a" too, yet the third pair ("c" vs "a") doesn't match.

Hints

Hint 1: Case and punctuation don't matter, so the first idea is: build a cleaned-up, lowercase, letters-and-digits-only copy, then compare it to its own reverse.

Approach

Optimal: Two pointers

Intuition

You don't need a cleaned copy to check symmetry — you need to compare the first meaningful character with the last meaningful character, then the second with the second-to-last, and so on. Keep one pointer at the very start and one at the very end. Skip a pointer inward past any character that isn't a letter or digit. Compare the two characters the pointers land on; if they don't match (ignoring case), it's not a palindrome. Otherwise step both pointers inward and repeat.

This does the same comparisons as the brute-force version but never builds a second string, which is what drops the space from O(n) to O(1).

Steps

  1. Set left = 0 and right = len(s) - 1.
  2. While left < right:
    • Move left forward while it points at a character that isn't a letter or digit.
    • Move right backward while it points at a character that isn't a letter or digit.
    • If the lowercase characters at left and right differ, return false.
    • Move left forward one step and right backward one step.
  3. If the loop finishes without a mismatch, return true.

Dry run

s = "race a car" (spaces are not letters or digits, so they're skipped)

left right s[left] s[right] match?
0 (r) 9 (r) r r yes
1 (a) 8 (a) a a yes
2 (c) 6 (c) c c yes
3 (e) 4 (skip space) → 4 (a) e a no → return false

Edge cases: a single space " " has left = 0 and right = 0 already, so the while left < right loop never runs and the function returns true immediately — an empty-after-cleaning string is vacuously a palindrome. A one-character string behaves the same way.

Complexity

Time O(n) - each pointer only moves inward and never backtracks, so together `left` and `right` visit each character at most once, for O(n) total work.

Space O(1) - only the two integer pointers are kept; the function never builds a second string, so memory use doesn't grow with the size of the input.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True


if __name__ == "__main__":
    print(str(Solution().isPalindrome("A man, a plan, a canal: Panama")).lower())  # true
    print(str(Solution().isPalindrome("race a car")).lower())  # false
    print(str(Solution().isPalindrome(" ")).lower())  # true
RecapThe whole problem in a few lines, for the night before
  • Spot it: palindrome check that ignores case, spaces and punctuation
  • Idea: two pointers from both ends; skip anything that is not a letter or digit, then compare lowercase
  • Cost: O(n) time, O(1) space
  • Trap: keep the pointers in bounds while skipping; an empty or symbols-only string is a palindrome

Interview follow-ups

  • What if you also had to return the cleaned string, not just true/false?

    You'd need to build it, which brings back the O(n) space the two-pointer trick avoided — there's no way to hand back the cleaned string without storing it somewhere. Build it once with the same one-pass filter-and-lowercase logic from the brute-force approach, and compare it to its reverse as before.

  • The string could be a live stream (e.g. arriving over a socket) instead of a fixed array. How would that change your approach?

    Two pointers from both ends need random access to the whole string up front, which a stream doesn't give you. You'd instead buffer the stream into a string as it arrives (or use a deque and pop from both ends once the whole message is buffered), so the algorithm doesn't change — only the fact that you must wait for the full input before starting the pointer walk.

Frequently asked questions

It never builds a second string. It only ever looks at two positions in the original string at a time, so the only extra memory it needs is the two integer pointers — that's O(1) regardless of how long the string is.

The problem defines "alphanumeric" using ASCII letters and digits, and the standard isalnum/Character.isLetterOrDigit checks follow that. An accented letter like "é" is not treated as alphanumeric by these checks, so it's skipped just like punctuation — worth calling out explicitly if you're asked to extend this to full Unicode text.

Two pointers scanning inward from both ends is the same shape as comparing a request and response checksum, validating that a config value is mirrored correctly, or checking a log line is well-formed from both edges — it's a cheap way to test whether you reach for O(1)-space techniques instead of defaulting to extra memory.