LeetCode 125 - Valid Palindrome

LeetCode Problem 125

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

This problem asks us to determine whether a given string is a palindrome after applying two transformations:

1. Convert all uppercase letters to lowercase.
2. Remove all non-alphanumeric characters.

An alphanumeric character is any English letter (a-z, A-Z) or digit (0-9). Characters such as spaces, punctuation marks, commas, colons, and symbols should be ignored completely.

After preprocessing, we must check whether the resulting string reads the same forward and backward. If it does, we return true; otherwise, we return false.

For example, the input string:

"A man, a plan, a canal: Panama"

becomes:

"amanaplanacanalpanama"

Since this string reads the same in both directions, the answer is true.

The constraints are important:

• The string length can be as large as 2 * 10^5
• The input consists only of printable ASCII characters

Because the input can be quite large, an inefficient solution may become too slow or consume unnecessary memory. We should aim for a linear time solution.

Several edge cases are worth identifying upfront. The string may contain only punctuation or spaces, meaning the filtered result becomes an empty string. The problem explicitly states that an empty string should be considered a palindrome. The input may also contain mixed uppercase and lowercase letters, requiring case normalization. Another tricky case involves numbers, since digits count as alphanumeric characters and must participate in the palindrome comparison.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to first build a cleaned version of the string.

We iterate through the original string and keep only alphanumeric characters, converting letters to lowercase as we go. Once we have this cleaned string, we create its reverse and compare the two strings.

If the cleaned string equals its reverse, then the input is a palindrome.

This approach is correct because the preprocessing exactly matches the problem definition. However, it uses extra memory to construct both the filtered string and its reversed version.

For very large inputs, creating multiple copies of the string is unnecessary and can be avoided.

Key Insight for the Optimal Approach

The key observation is that we do not actually need to construct the cleaned string.

Instead, we can use the two pointers technique directly on the original string:

• One pointer starts at the beginning.
• One pointer starts at the end.
• Skip any non-alphanumeric characters.
• Compare valid characters after converting them to lowercase.
• Move inward after successful comparisons.

This works because a palindrome is fundamentally a symmetry check. We only care whether matching characters at mirrored positions are equal after normalization.

By processing characters in-place, we avoid building extra strings and reduce memory usage.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Build filtered string and compare with reversed version
Optimal	O(n)	O(1)	Two pointers process string in-place

Algorithm Walkthrough

1. Initialize two pointers, left at the beginning of the string and right at the end.

These pointers represent the characters we want to compare from opposite ends of the string. 2. Skip non-alphanumeric characters from the left side.

If s[left] is not a letter or digit, increment left. Since these characters should be ignored according to the problem statement, they do not participate in palindrome checking. 3. Skip non-alphanumeric characters from the right side.

Similarly, if s[right] is not alphanumeric, decrement right. 4. Compare the normalized characters.

Once both pointers are positioned at valid characters, convert both to lowercase and compare them.

If they are different, immediately return false, since a palindrome requires mirrored characters to match. 5. Move both pointers inward.

If the characters match, increment left and decrement right to continue checking the remaining portion of the string. 6. Continue until the pointers cross.

If all valid character pairs match, return true.

Why it works

The algorithm maintains the invariant that every pair of valid characters outside the current [left, right] range has already been verified to match. At each step, we compare the next valid mirrored characters after normalization. If any pair differs, the string cannot be a palindrome. If the pointers cross without finding a mismatch, then every mirrored pair matched, proving the string is a valid palindrome.

Python Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = 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 s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

The implementation follows the algorithm exactly.

We first initialize two pointers, left and right, at opposite ends of the string. The main while loop continues as long as the pointers have not crossed.

Inside the loop, we skip invalid characters using isalnum(), which checks whether a character is alphanumeric. This ensures punctuation, spaces, and symbols are ignored.

After positioning both pointers on valid characters, we normalize the comparison using lower(). If the characters differ, we immediately return False.

If they match, both pointers move inward to continue checking the remaining substring.

If the loop completes without detecting a mismatch, every relevant character pair matched successfully, so we return True.

Go Solution

import "unicode"

func isPalindrome(s string) bool {
	left := 0
	right := len(s) - 1

	for left < right {
		for left < right && !unicode.IsLetter(rune(s[left])) && !unicode.IsDigit(rune(s[left])) {
			left++
		}

		for left < right && !unicode.IsLetter(rune(s[right])) && !unicode.IsDigit(rune(s[right])) {
			right--
		}

		leftChar := unicode.ToLower(rune(s[left]))
		rightChar := unicode.ToLower(rune(s[right]))

		if leftChar != rightChar {
			return false
		}

		left++
		right--
	}

	return true
}

The Go implementation follows the same two pointer strategy as Python.

One implementation difference is character handling. Go strings are byte sequences, so individual characters are accessed using indexing. Since the problem guarantees printable ASCII input, indexing by byte is safe.

Go does not provide an isalnum() equivalent directly on strings, so we use unicode.IsLetter() and unicode.IsDigit() to check validity. We also use unicode.ToLower() for case-insensitive comparison.

Unlike Python, there is no distinction between nil and empty strings here, because the input is guaranteed to be a valid string.

Worked Examples

Example 1

Input:

"A man, a plan, a canal: Panama"

Step	Left Pointer	Right Pointer	Character Comparison	Action
1	A	a	a == a	Move inward
2	space → m	m	m == m	Move inward
3	a	a	a == a	Move inward
4	n	n	n == n	Move inward
5	punctuation skipped	punctuation skipped	Continue	Continue
...	...	...	All pairs match	Continue
Final	pointers cross			Return true

The algorithm keeps skipping spaces and punctuation while comparing only normalized alphanumeric characters. Since every mirrored pair matches, the result is true.

Example 2

Input:

"race a car"

Step	Left Pointer	Right Pointer	Character Comparison	Result
1	r	r	r == r	Continue
2	a	a	a == a	Continue
3	c	c	c == c	Continue
4	e	a	e != a	Return false

A mismatch occurs before the pointers meet, proving the string is not a palindrome.

Example 3

Input:

" "

Step	Left Pointer	Right Pointer	Action
1	0	0	Loop never executes
Final			Return true

After removing non-alphanumeric characters, the string becomes empty, which is considered a palindrome.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited at most once by either pointer
Space	O(1)	Only a few variables are used regardless of input size

The time complexity is linear because each pointer moves inward without revisiting characters. Even though there are nested loops for skipping invalid characters, every character is skipped at most once.

The space complexity is constant because no additional data structures proportional to the input size are allocated.

Test Cases

solution = Solution()

assert solution.isPalindrome("A man, a plan, a canal: Panama") is True  # classic valid palindrome
assert solution.isPalindrome("race a car") is False  # mismatch in middle
assert solution.isPalindrome(" ") is True  # empty after filtering
assert solution.isPalindrome("") is True  # empty string edge case
assert solution.isPalindrome("a") is True  # single character
assert solution.isPalindrome("ab") is False  # simple non-palindrome
assert solution.isPalindrome("aa") is True  # simple palindrome
assert solution.isPalindrome("0P") is False  # digit and letter mismatch
assert solution.isPalindrome("Madam") is True  # case insensitive match
assert solution.isPalindrome("No 'x' in Nixon") is True  # punctuation ignored
assert solution.isPalindrome(".,") is True  # only punctuation
assert solution.isPalindrome("12321") is True  # numeric palindrome
assert solution.isPalindrome("12345") is False  # numeric non-palindrome
assert solution.isPalindrome("Able was I ere I saw Elba") is True  # phrase palindrome
assert solution.isPalindrome("a,b,c,c,b,a") is True  # punctuation ignored

Test	Why
"A man, a plan, a canal: Panama"	Valid palindrome with spaces and punctuation
"race a car"	Standard negative case
" "	Empty after filtering
""	Empty string boundary case
"a"	Single character input
"ab"	Smallest non-palindrome
"aa"	Smallest palindrome
"0P"	Digit and letter mismatch
"Madam"	Case insensitivity
"No 'x' in Nixon"	Mixed punctuation and casing
".,"	Only ignored characters
"12321"	Numeric palindrome
"12345"	Numeric non-palindrome
"Able was I ere I saw Elba"	Long phrase palindrome
"a,b,c,c,b,a"	Valid palindrome with separators

Edge Cases

Strings Containing Only Non-Alphanumeric Characters

An input such as "!@#$" can be tricky because all characters are ignored. A naive implementation might accidentally return false if it expects at least one valid character. In this solution, both pointers skip invalid characters until they cross, and the function correctly returns true.

Mixed Case Characters

Inputs such as "RaceCar" should still count as palindromes despite different letter casing. Without normalization, 'R' and 'r' would not match. The implementation solves this by converting both characters to lowercase before comparison.

Strings Containing Numbers

Digits are part of the palindrome definition and must not be ignored. An input like "12321" should return true, while "12a21" should return false. Because the implementation treats both letters and digits as valid alphanumeric characters, numeric palindromes are handled correctly.