125. Valid Palindrome - Explanation

Problem Link

Description

Given a string s, return true if it is a palindrome, otherwise return false.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Note: Alphanumeric characters consist of letters (A-Z, a-z) and numbers (0-9).

Example 1:

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

Output: true

Explanation: After considering only alphanumerical characters we have "wasitacaroracatisaw", which is a palindrome.

Example 2:

Input: s = "tab a cat"

Output: false

Explanation: "tabacat" is not a palindrome.

Constraints:

  • 1 <= s.length <= 1000
  • s is made up of only printable ASCII characters.


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the length of the input string.


Hint 1

A brute force solution would be to create a copy of the string, reverse it, and then check for equality. This would be an O(n) solution with extra space. Can you think of a way to do this without O(n) space?


Hint 2

Can you find the logic by observing the definition of pallindrome or from the brute force solution?


Hint 3

A palindrome string is a string that is read the same from the start as well as from the end. This means the character at the start should match the character at the end at the same index. We can use the two pointer algorithm to do this efficiently.


Company Tags

Meta30 Google6 Apple6 Microsoft4 Bloomberg4 Yandex2 Amazon6 Oracle3 Adobe2 Tiktok2 Cognizant2 Axon2 BCG11 TCS6 Uber5 Toast4 EPAM Systems3 Zoho3 Accenture3 Spotify3 SAP3 Infosys2


1. Reverse String

Intuition

To check if a string is a palindrome, we only care about letters and digits—everything else can be ignored.
We can build a cleaned version of the string that contains only alphanumeric characters, all converted to lowercase for consistency.
Once we have this cleaned string, the problem becomes very simple:
a string is a palindrome if it is exactly the same as its reverse.

Algorithm

  1. Create an empty string newStr.
  2. Loop through each character c in the input string:
    • If c is alphanumeric, convert it to lowercase and add it to newStr.
  3. Compare newStr with its reverse (newStr[::-1]):
    • If they are equal, return true.
    • Otherwise, return false.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        newStr = ''
        for c in s:
            if c.isalnum():
                newStr += c.lower()
        return newStr == newStr[::-1]

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Two Pointers

Intuition

Instead of building a new string, we can check the palindrome directly in-place using two pointers.
One pointer starts at the beginning (l) and the other at the end (r).
We move both pointers inward, skipping any characters that are not letters or digits.
Whenever both pointers point to valid characters, we compare them in lowercase form.
If at any point they differ, the string is not a palindrome.
This method avoids extra space and keeps the logic simple and efficient.

Algorithm

  1. Initialize two pointers:
    • l at the start of the string,
    • r at the end of the string.
  2. While l is less than r:
    • Move l forward until it points to an alphanumeric character.
    • Move r backward until it points to an alphanumeric character.
    • Compare the lowercase characters at l and r:
      • If they don't match, return false.
    • Move both pointers inward: l += 1, r -= 1.
  3. If the loop finishes without mismatches, return true.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            while l < r and not self.alphaNum(s[l]):
                l += 1
            while r > l and not self.alphaNum(s[r]):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l, r = l + 1, r - 1
        return True

    def alphaNum(self, c):
        return (ord('A') <= ord(c) <= ord('Z') or
                ord('a') <= ord(c) <= ord('z') or
                ord('0') <= ord(c) <= ord('9'))

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

Common Pitfalls

Not Skipping Non-Alphanumeric Characters

The problem requires ignoring all characters that are not letters or digits. Forgetting to skip spaces, punctuation, and special characters will cause false negatives. For example, "A man, a plan, a canal: Panama" should be recognized as a palindrome, but including the spaces and punctuation in the comparison will incorrectly return false.

Case Sensitivity

Letters must be compared in a case-insensitive manner. Comparing 'A' directly with 'a' will return false even though they should be treated as equal. Always convert both characters to the same case (lowercase or uppercase) before comparing.