All Problems
EasyTwo PointersString

Valid Palindrome

Time Complexity
O(n)
Space Complexity
O(1)

📋Problem Statement

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.

💡Examples

1Example 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.
2Example 2
Input: s = "tab a cat"
Output: false
Explanation: "tabacat" is not a palindrome.
3Example 3
Input: s = "0P"
Output: false
Explanation: "0p" - digit 0 and letter P are not equal, so it's not a palindrome.

⚠️Constraints

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

🧠Approach

Use the two-pointer technique to compare characters from both ends: 1. Initialize two pointers: left at start, right at end 2. Skip any non-alphanumeric characters by moving pointers 3. Compare characters at both pointers (case-insensitive) 4. If they don't match, return false 5. Move both pointers toward the center 6. If all comparisons pass, return true Key insight: Handle both letters AND digits as valid characters. A common mistake is to only check for letters, which fails test cases like "0P".

✨Solution

func isPalindrome(s string) bool {
    start := 0
    end := len(s) - 1
    runes := []rune(s)
    
    for start < end {
        // Skip non-alphanumeric characters from start
        if !(unicode.IsLetter(runes[start]) || unicode.IsDigit(runes[start])) {
            start++
            continue
        }
        // Skip non-alphanumeric characters from end
        if !(unicode.IsLetter(runes[end]) || unicode.IsDigit(runes[end])) {
            end--
            continue
        }
        // Compare characters (case-insensitive)
        if unicode.ToLower(runes[start]) != unicode.ToLower(runes[end]) {
            return false
        }
        start++
        end--
    }
    return true
}

🎯Key Points

  • 1Two-pointer technique is optimal for palindrome checking
  • 2Must handle BOTH letters AND digits (not just letters)
  • 3Case-insensitive comparison is required
  • 4Skip non-alphanumeric characters without breaking the loop
  • 5O(1) space because we modify nothing, just use pointers
Browse More Problems