DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Valid Palindrome

easyTwo pointers Must-do

Problem statement

You are given a string s. Ignore every character that is not a letter or a digit, and treat uppercase and lowercase letters as equal. Return true if what remains reads the same forwards and backwards, otherwise false.

An empty result (for example, a string of only punctuation) counts as a palindrome.

Examples

Example 1

Input: s = "Was it a car or a cat I saw?"

Output: true

Explanation: Cleaned up, it becomes wasitacaroracatisaw, which is the same reversed.

Example 2

Input: s = "deploy-01"

Output: false

Explanation: Cleaned up, it becomes deploy01, and reversed that is 10yolped.

Hints

Approach

Compare from both ends at once, skipping characters that do not count, with no copy at all.

  1. Put left at the start and right at the end.
  2. While left < right: move left forward past non-alphanumeric characters, and right backward the same way.
  3. Compare the two characters in lowercase. If they differ, return false.
  4. Move both pointers inward and repeat.
  5. Return true.

The skip loops also check left < right, so a string of only punctuation cannot push a pointer out of range.

ComplexityTime O(n)Space O(1)
Python
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

Follow-up questions

  • Return true if the string can become a palindrome by deleting at most one character.
  • Find the longest palindromic substring.

Frequently asked questions

Without it, a string like "!!" would move left past the end of the string while looking for a letter. The extra check keeps both pointers inside the string.

Yes. Digits are kept and must match like letters do, which is why "deploy-01" fails: 0 and 1 end up on opposite sides.

Normalising input before comparing it is routine: lowercasing hostnames, stripping punctuation from tags, or ignoring whitespace in config values. The two-pointer scan is also the base of many in-place string and array problems.