Check if String is Palindrome

Determine if a string reads the same forwards and backwards, ignoring case and non-alphanumeric characters.

Language Selection

Choose your preferred programming language

Showing: Python

Check if String is Palindrome

Problem Statement

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward.

Examples

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome

Example 3:

Input: s = " "
Output: true
Explanation: Empty string is considered a palindrome

Constraints

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

Approach 1: Two Pointers

Algorithm

Use two pointers starting from both ends of the string, moving towards the center while comparing characters.

Steps:

Initialize left pointer at start and right pointer at end
Skip non-alphanumeric characters
Compare characters (case-insensitive)
Move pointers towards center
Return true if all comparisons pass

Implementation

Python:

def is_palindrome(s):
    """
    Check if string is palindrome using two pointers
    Time: O(n)
    Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric characters from left
        while left < right and not s[left].isalnum():
            left += 1
        
        # Skip non-alphanumeric characters from right
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

Java:

class Solution {
    /**
     * Check if string is palindrome using two pointers
     * Time: O(n)
     * Space: O(1)
     */
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            // Skip non-alphanumeric characters from left
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            
            // Skip non-alphanumeric characters from right
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            
            // Compare characters (case-insensitive)
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
}

Go:

// isPalindrome - Check if string is palindrome using two pointers
// Time: O(n)
// Space: O(1)
func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    
    for left < right {
        // Skip non-alphanumeric characters from left
        for left < right && !isAlphanumeric(s[left]) {
            left++
        }
        
        // Skip non-alphanumeric characters from right
        for left < right && !isAlphanumeric(s[right]) {
            right--
        }
        
        // Compare characters (case-insensitive)
        if toLowerCase(s[left]) != toLowerCase(s[right]) {
            return false
        }
        
        left++
        right--
    }
    
    return true
}

func isAlphanumeric(c byte) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}

func toLowerCase(c byte) byte {
    if c >= 'A' && c <= 'Z' {
        return c + 32
    }
    return c
}

JavaScript:

/**
 * Check if string is palindrome using two pointers
 * Time: O(n)
 * Space: O(1)
 */
function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    
    while (left < right) {
        // Skip non-alphanumeric characters from left
        while (left < right && !isAlphanumeric(s[left])) {
            left++;
        }
        
        // Skip non-alphanumeric characters from right
        while (left < right && !isAlphanumeric(s[right])) {
            right--;
        }
        
        // Compare characters (case-insensitive)
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

function isAlphanumeric(char) {
    return /[a-zA-Z0-9]/.test(char);
}

C#:

public class Solution {
    /// <summary>
    /// Check if string is palindrome using two pointers
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public bool IsPalindrome(string s) {
        int left = 0, right = s.Length - 1;
        
        while (left < right) {
            // Skip non-alphanumeric characters from left
            while (left < right && !char.IsLetterOrDigit(s[left])) {
                left++;
            }
            
            // Skip non-alphanumeric characters from right
            while (left < right && !char.IsLetterOrDigit(s[right])) {
                right--;
            }
            
            // Compare characters (case-insensitive)
            if (char.ToLower(s[left]) != char.ToLower(s[right])) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(1)

Approach 2: Clean and Reverse

Algorithm

Clean the string by removing non-alphanumeric characters and converting to lowercase, then compare with its reverse.

Steps:

Clean the string (remove non-alphanumeric, convert to lowercase)
Compare the cleaned string with its reverse
Return true if they are equal

Implementation

Python:

def is_palindrome_clean(s):
    """
    Check if string is palindrome by cleaning and reversing
    Time: O(n)
    Space: O(n)
    """
    # Clean the string
    cleaned = ''.join(char.lower() for char in s if char.isalnum())
    
    # Compare with reverse
    return cleaned == cleaned[::-1]

Java:

class Solution {
    /**
     * Check if string is palindrome by cleaning and reversing
     * Time: O(n)
     * Space: O(n)
     */
    public boolean isPalindromeClean(String s) {
        // Clean the string
        StringBuilder cleaned = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                cleaned.append(Character.toLowerCase(c));
            }
        }
        
        // Compare with reverse
        return cleaned.toString().equals(cleaned.reverse().toString());
    }
}

Go:

// isPalindromeClean - Check if string is palindrome by cleaning and reversing
// Time: O(n)
// Space: O(n)
func isPalindromeClean(s string) bool {
    // Clean the string
    var cleaned strings.Builder
    for _, c := range s {
        if isAlphanumeric(byte(c)) {
            cleaned.WriteRune(toLowerCase(byte(c)))
        }
    }
    
    cleanedStr := cleaned.String()
    
    // Compare with reverse
    return cleanedStr == reverse(cleanedStr)
}

func reverse(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

JavaScript:

/**
 * Check if string is palindrome by cleaning and reversing
 * Time: O(n)
 * Space: O(n)
 */
function isPalindromeClean(s) {
    // Clean the string
    const cleaned = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
    
    // Compare with reverse
    return cleaned === cleaned.split('').reverse().join('');
}

C#:

public class Solution {
    /// <summary>
    /// Check if string is palindrome by cleaning and reversing
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public bool IsPalindromeClean(string s) {
        // Clean the string
        var cleaned = new StringBuilder();
        foreach (char c in s) {
            if (char.IsLetterOrDigit(c)) {
                cleaned.Append(char.ToLower(c));
            }
        }
        
        string cleanedStr = cleaned.ToString();
        
        // Compare with reverse
        return cleanedStr == new string(cleanedStr.Reverse().ToArray());
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(n) for the cleaned string

Key Insights

Two Pointers: The most space-efficient approach uses two pointers moving towards the center
Character Filtering: Need to handle non-alphanumeric characters and case differences
Edge Cases: Empty strings and single characters are palindromes
Space Trade-off: Clean-and-reverse uses more space but is more readable

Edge Cases

Empty string: Considered a palindrome
Single character: Always a palindrome
Only non-alphanumeric: Empty after cleaning, considered palindrome
Mixed case: “RaceCar” should return true
Special characters: “A man, a plan, a canal: Panama” should return true

Test Cases

# Test cases
assert is_palindrome("A man, a plan, a canal: Panama") == True
assert is_palindrome("race a car") == False
assert is_palindrome(" ") == True
assert is_palindrome("racecar") == True
assert is_palindrome("RaceCar") == True
assert is_palindrome("A") == True
assert is_palindrome("") == True
assert is_palindrome("No 'x' in Nixon") == True

Follow-up Questions

Longest Palindromic Substring: Find the longest palindromic substring
Valid Palindrome II: Can make at most one character deletion
Palindrome Partitioning: Partition string into palindromic substrings
Palindrome Number: Check if a number is palindrome
Longest Palindromic Subsequence: Find longest palindromic subsequence

Common Mistakes

Case sensitivity: Forgetting to handle case differences
Non-alphanumeric: Not properly filtering special characters
Empty string: Not handling empty string edge case
Index bounds: Going out of bounds in two-pointer approach
Character comparison: Comparing original characters instead of cleaned ones

Interview Tips

Clarify requirements: Ask about case sensitivity and special characters
Start simple: Begin with basic palindrome check, then add complexity
Handle edge cases: Always consider empty strings and single characters
Optimize space: Two-pointer approach is more space-efficient
Test thoroughly: Walk through examples step by step

Variations

Strict palindrome: Only letters, case-sensitive
Palindrome with deletions: Allow removing characters
Palindrome with insertions: Allow adding characters
Case-insensitive: Ignore case differences
Alphanumeric only: Consider only letters and numbers