We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Palindrome

Number: 125

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Apple, Bloomberg, Yandex, Cisco, Oracle, tcs, Cadence, Microsoft, Goldman Sachs, TikTok, Zoho, Adobe, EPAM Systems, ServiceNow, Uber, Wayfair, Tesla, Infosys, Softwire, Toast, Turing, Zenefits

Problem Description

Determine whether a given string is a palindrome after converting all uppercase letters into lowercase and removing all non-alphanumeric characters. An empty string is considered a palindrome.

Key Insights

  • Use two pointers (one starting at the beginning and one at the end) to compare characters.
  • Skip characters that are not alphanumeric.
  • Compare characters in a case-insensitive manner.
  • Continue until the pointers meet or cross.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as each character is processed at most once. Space Complexity: O(1), using only a few extra variables for pointers and temporary comparisons.

Solution

The solution employs a two-pointer approach:

  1. Initialize two pointers: one at the start (left) and one at the end (right) of the string.
  2. Skip any non-alphanumeric characters using these pointers.
  3. Convert the remaining characters at each pointer to lowercase and compare them.
  4. If any mismatch is found, return false; otherwise, continue until the pointers cross.
  5. Return true if all corresponding characters match. This method efficiently checks for a palindrome without needing additional space for a filtered string.

Code Solutions

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Initialize two pointers at the beginning and end of the string
        left, right = 0, len(s) - 1
        while left < right:
            # Skip non-alphanumeric characters from the left
            while left < right and not s[left].isalnum():
                left += 1
            # Skip non-alphanumeric characters from the right
            while left < right and not s[right].isalnum():
                right -= 1
            # Compare the characters in lowercase
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True
← Back to All Questions