Valid Palindrome

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

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

Examples:

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

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Input: s = "race a car"

Output: false

Explanation: "raceacar" is not a palindrome.

Input: s = ""

Output: true

Explanation: s is an empty string after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Constraints

1 <= s.length <= 2 * 10⁵
s consists only of printable ASCII characters.

Editorial

Intuition:

The key insight is that a palindrome reads the same forwards and backwards. By using two pointers starting from both ends and skipping non-alphanumeric characters, we can compare characters in a case-insensitive manner without extra space.

Approach:

Initialize two pointers: left at the start and right at the end of the string.
While left < right, move each pointer inward until it points to an alphanumeric character, then compare the lowercase versions. If they differ, return false.
If all comparisons match, return true after the pointers meet or cross.

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            while (left < right && !isalnum(s[left])) left++;
            while (left < right && !isalnum(s[right])) right--;
            if (left < right) {
                if (tolower(s[left]) != tolower(s[right])) return false;
                left++;
                right--;
            }
        }
        return true;
    }
};
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
                left++;
                right--;
            }
        }
        return true;
    }
}
class Solution:
    def isPalindrome(self, s):
        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 left < right:
                if s[left].lower() != s[right].lower():
                    return False
                left += 1
                right -= 1
        return True
class Solution {
    isPalindrome(s) {
        let left = 0, right = s.length - 1;
        while (left < right) {
            while (left < right && !this.isAlphanumeric(s[left])) left++;
            while (left < right && !this.isAlphanumeric(s[right])) right--;
            if (left < right) {
                if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
                left++;
                right--;
            }
        }
        return true;
    }
    isAlphanumeric(c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the length of the string. Each character is visited at most once by one of the pointers.

Space Complexity: O(1), only two pointers and constant extra space are used.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories