125. Valid Palindrome

At a Glance

• Topic: two-pointers
• Pattern: Two Pointers
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Microsoft, Apple
• Frequency: High
• LeetCode: 125

Problem (one-liner)

After lowercasing and keeping only alphanumeric characters, decide if a string reads the same forward and backward. Return a boolean.

Recognition Cues

• "Palindrome" on a string with possible spaces / punctuation
• "Alphanumeric only" or "ignore case"
• Two ends that should meet in the middle

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n) time / O(n) space — filter to a new string, compare to its reverse.
• Better — O(n) time / O(n) space — two pointers on a pre-built clean slice of runes/bytes.
• Optimal — O(n) time / O(1) space — one pass: two pointers on the original string, skip non-alphanumeric, compare case-insensitively.

Optimal Solution

Go

func isPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		for left < right && !isAlnum(s[left]) {
			left++
		}
		for left < right && !isAlnum(s[right]) {
			right--
		}
		if toLower(s[left]) != toLower(s[right]) {
			return false
		}
		left++
		right--
	}
	return true
}

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

func toLower(b byte) byte {
	if b >= 'A' && b <= 'Z' {
		return b + ('a' - 'A')
	}
	return b
}

JavaScript

function isPalindrome(text) {
	let left = 0;
	let right = text.length - 1;
	while (left < right) {
		while (left < right && !isAlphanumeric(text[left])) {
			left++;
		}
		while (left < right && !isAlphanumeric(text[right])) {
			right--;
		}
		if (normalize(text[left]) !== normalize(text[right])) {
			return false;
		}
		left++;
		right--;
	}
	return true;
}

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

function normalize(char) {
	return char.toLowerCase();
}

Walkthrough

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

Invariant: characters strictly inside [left, right] are already matched pairs; only the shrinking window remains.

Edge Cases

• Empty string after filtering (treat as palindrome)
• Single character
• All non-alphanumeric
• Mixed case and digits

Pitfalls

• Comparing raw indices without skipping junk characters
• Off-by-one when advancing both pointers after a match
• Unicode: problem is ASCII-oriented on LeetCode; using full Unicode normalization changes behavior

Similar Problems

• 680. Valid Palindrome II — allow one skip when mismatch.
• 167. Two Sum II — Input Array Is Sorted — same inward convergence on sorted data.
• 11. Container With Most Water — two pointers from both ends on array values.

Variants

• Unicode letters only — extend isAlnum / normalization.
• Longest palindromic substring — expand from center or DP.
• Remove minimum characters to get palindrome — different problem (edit distance style).

Mind-Map Tags

#two-pointers #palindrome #alphanumeric #inward-convergence #string