125. Valid Palindrome (Easy)

Problem

Given a string s, return true if it reads the same forwards and backwards after removing non-alphanumeric characters and lowercasing the rest.

Examples

• s = "A man, a plan, a canal: Panama" → true
• s = "race a car" → false
• s = " " → true (empty after cleaning)

LeetCode 125 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, clean, then compare to reverse

Filter to alphanumerics, lowercase, and compare to the reversed string.

Python

def is_palindrome(s: str) -> bool:
    cleaned = "".join(ch.lower() for ch in s if ch.isalnum())  # L1: O(n) filter+join
    return cleaned == cleaned[::-1]                             # L2: O(n) reverse+compare

TypeScript

function isPalindrome(s: string): boolean {
    const cleaned = Array.from(s)
        .filter(ch => /[a-z0-9]/i.test(ch))
        .map(ch => ch.toLowerCase())
        .join('');                                    // L1: O(n) filter+join
    return cleaned === cleaned.split('').reverse().join(''); // L2: O(n) reverse+compare
}

Go

func isPalindrome(s string) bool {
    cleaned := []rune{}
    for _, ch := range s {
        if unicode.IsLetter(ch) || unicode.IsDigit(ch) {
            cleaned = append(cleaned, unicode.ToLower(ch))
        }
    }
    for l, r := 0, len(cleaned)-1; l < r; l, r = l+1, r-1 {
        if cleaned[l] != cleaned[r] {
            return false
        }
    }
    return true
}

Swift

final class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let cleaned = s.filter { $0.isLetter || $0.isNumber }.map(normalized)
        return cleaned == Array(cleaned.reversed())
    }

    private func normalized(_ character: Character) -> Character {
        Character(String(character).lowercased())
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (filter + join)	$O(n)$	1	$O(n)$ ← dominates
L2 (reverse + compare)	$O(n)$	1	$O(n)$

Both steps are linear; neither dominates asymptotically.

Complexity

• Time: $O(n)$, driven by L1/L2 (two linear passes).
• Space: $O(n)$. The cleaned string and its reverse.

Direct and clear, but uses an extra $O(n)$ allocation where $O(1)$ is achievable.

Approach 2: Clean, then two pointers

Build the cleaned string, then walk from both ends. Same asymptotics as Approach 1 with an early-exit on the first mismatch.

Python

def is_palindrome(s: str) -> bool:
    cleaned = [ch.lower() for ch in s if ch.isalnum()]  # L1: O(n) filter
    l, r = 0, len(cleaned) - 1                          # L2: O(1) init pointers
    while l < r:                                         # L3: at most n/2 iterations
        if cleaned[l] != cleaned[r]:                     # L4: O(1) compare
            return False                                 # L5: O(1) early exit
        l, r = l + 1, r - 1                             # L6: O(1) advance both
    return True

TypeScript

function isPalindrome(s: string): boolean {
    const cleaned = Array.from(s).filter(ch => /[a-z0-9]/i.test(ch)).map(ch => ch.toLowerCase()); // L1: O(n) filter
    let l = 0, r = cleaned.length - 1;                  // L2: O(1) init pointers
    while (l < r) {                                      // L3: at most n/2 iterations
        if (cleaned[l] !== cleaned[r]) return false;     // L4/L5: O(1) compare + early exit
        l++;                                             // L6: O(1) advance both
        r--;
    }
    return true;
}

Go

func isPalindrome(s string) bool {
    cleaned := []rune{}
    for _, ch := range s {
        if unicode.IsLetter(ch) || unicode.IsDigit(ch) {
            cleaned = append(cleaned, unicode.ToLower(ch)) // L1: O(n) filter
        }
    }
    l, r := 0, len(cleaned)-1                             // L2: O(1) init pointers
    for l < r {                                            // L3: at most n/2 iterations
        if cleaned[l] != cleaned[r] {                      // L4: O(1) compare
            return false                                   // L5: O(1) early exit
        }
        l++                                                // L6: O(1) advance both
        r--
    }
    return true
}

Swift

final class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let cleaned = s.filter { $0.isLetter || $0.isNumber }.map(normalized)
        guard !cleaned.isEmpty else { return true }
        var left = 0
        var right = cleaned.count - 1
        while left < right {
            if cleaned[left] != cleaned[right] { return false }
            left += 1
            right -= 1
        }
        return true
    }

    private func normalized(_ character: Character) -> Character {
        Character(String(character).lowercased())
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (filter)	$O(n)$	1	$O(n)$ ← dominates
L2 (init pointers)	$O(1)$	1	$O(1)$
L3-L6 (two-pointer scan)	$O(1)$	at most n/2	$O(n)$

The filter pass dominates; the pointer scan is at most half the cleaned length.

Complexity

• Time: $O(n)$, driven by L1 (filter) and L3/L4 (scan). Best case $O(1)$ (first mismatch).
• Space: $O(n)$. The cleaned list.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Two pointers, skip non-alphanumerics in-place (optimal)

Walk both ends of the original string, skipping over non-alphanumeric characters on the fly. No extra allocation.

Python

def is_palindrome(s: str) -> bool:
    l, r = 0, len(s) - 1                # L1: O(1) init pointers
    while l < r:                         # L2: at most n steps total
        while l < r and not s[l].isalnum():  # L3: skip non-alnum on left
            l += 1                       # L4: O(1)
        while l < r and not s[r].isalnum():  # L5: skip non-alnum on right
            r -= 1                       # L6: O(1)
        if s[l].lower() != s[r].lower():  # L7: O(1) compare
            return False                  # L8: O(1) early exit
        l, r = l + 1, r - 1             # L9: O(1) advance both
    return True

TypeScript

function isPalindrome(s: string): boolean {
    let l = 0, r = s.length - 1;                        // L1: O(1) init pointers
    while (l < r) {                                      // L2: at most n steps total
        while (l < r && !/[a-z0-9]/i.test(s[l])) l++;  // L3/L4: skip non-alnum on left
        while (l < r && !/[a-z0-9]/i.test(s[r])) r--;  // L5/L6: skip non-alnum on right
        if (s[l].toLowerCase() !== s[r].toLowerCase())  // L7: O(1) compare
            return false;                                // L8: O(1) early exit
        l++;                                             // L9: O(1) advance both
        r--;
    }
    return true;
}

Go

func isPalindrome(s string) bool {
    runes := []rune(s)
    l, r := 0, len(runes)-1                              // L1: O(1) init pointers
    for l < r {                                           // L2: at most n steps total
        for l < r && !unicode.IsLetter(runes[l]) && !unicode.IsDigit(runes[l]) {
            l++                                           // L3/L4: skip non-alnum on left
        }
        for l < r && !unicode.IsLetter(runes[r]) && !unicode.IsDigit(runes[r]) {
            r--                                           // L5/L6: skip non-alnum on right
        }
        if unicode.ToLower(runes[l]) != unicode.ToLower(runes[r]) { // L7: O(1) compare
            return false                                  // L8: O(1) early exit
        }
        l++                                               // L9: O(1) advance both
        r--
    }
    return true
}

Swift

final class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let characters = Array(s)
        guard !characters.isEmpty else { return true }
        var left = 0
        var right = characters.count - 1
        while left < right {
            while left < right && !isAlphanumeric(characters[left]) { left += 1 }
            while left < right && !isAlphanumeric(characters[right]) { right -= 1 }
            if normalized(characters[left]) != normalized(characters[right]) { return false }
            left += 1
            right -= 1
        }
        return true
    }

    private func isAlphanumeric(_ character: Character) -> Bool {
        character.isLetter || character.isNumber
    }

    private func normalized(_ character: Character) -> Character {
        Character(String(character).lowercased())
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2 (outer loop)	$O(1)$	at most n	$O(n)$
L3-L6 (skip non-alnum)	$O(1)$ per step	n total	$O(n)$ ← dominates
L7-L9 (compare + advance)	$O(1)$	at most n/2	$O(n)$

Each character in s is touched at most once (either skipped in L3/L5 or compared in L7). Total work is $O(n)$.

Complexity

• Time: $O(n)$, driven by L3-L6 (each character visited once). Each index is visited at most once.
• Space: $O(1)$. No auxiliary structures.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Clean + reverse compare	$O(n)$	$O(n)$
Clean + two pointers	$O(n)$	$O(n)$
Two pointers in place	$O(n)$	$O(1)$

Same Big-O on time, but the in-place two-pointer version is the canonical “optimal-space” answer.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_valid_palindrome.py and run.
# Uses the canonical implementation (Approach 3: two pointers in place).

def is_palindrome(s: str) -> bool:
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum():
            l += 1
        while l < r and not s[r].isalnum():
            r -= 1
        if s[l].lower() != s[r].lower():
            return False
        l, r = l + 1, r - 1
    return True

def _run_tests():
    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("") == True
    assert is_palindrome("a") == True
    assert is_palindrome("aa") == True
    assert is_palindrome("ab") == False
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function isPalindrome(s: string): boolean {
    let l = 0, r = s.length - 1;
    while (l < r) {
        while (l < r && !/[a-z0-9]/i.test(s[l])) l++;
        while (l < r && !/[a-z0-9]/i.test(s[r])) r--;
        if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
        l++;
        r--;
    }
    return true;
}

console.assert(isPalindrome('A man, a plan, a canal: Panama') === true);
console.assert(isPalindrome('race a car') === false);
console.assert(isPalindrome(' ') === true);
console.assert(isPalindrome('') === true);
console.assert(isPalindrome('a') === true);
console.assert(isPalindrome('aa') === true);
console.assert(isPalindrome('ab') === false);
console.log('all tests pass');

Related data structures

• Strings, input; in-place traversal with isalnum

Related concepts

• Two Pointers, the two index invariant that shrinks or coordinates positions without nested loops.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.