Valid Palindrome

LeetCode 125 | Difficulty: Easy

Easy

Problem Description

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

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: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

- `1 <= s.length <= 2 * 10^5`

- `s` consists only of printable ASCII characters.

Topics: Two Pointers, String

---

Approach

Direct Approach

This problem can typically be solved with straightforward iteration or simple data structure usage. Focus on correctness first, then optimize.

When to use

Basic problems that test fundamental programming skills.

---

Solutions

Solution 1: C# (Best: 88 ms)

Metric	Value
Runtime	88 ms
Memory	N/A
Date	2018-07-04

Solution

public class Solution {
    public bool IsPalindrome(string s)
    {
        if(string.IsNullOrEmpty(s)) return true;
        s = s.ToLower();
        int i=0, j=s.Length-1;
        while(i<j)
        {
            while(i<j && !IsAlphnumeric(s[i])) i++;
            while(i<j && !IsAlphnumeric(s[j])) j--;
            if(i<j && s[i]!=s[j]) return false;
            i++;
            j--;
        }
        return true;
    }

public bool IsAlphnumeric(char c)
{
    return (c>='0' && c<='9') ||  (c>='a' && c<='z') ||  (c>='A' && c<='Z');
}
}

📜 1 more C# submission(s)

Submission (2018-03-25) — 156 ms, N/A

public class Solution {
    public bool IsPalindrome(string s) {
            if(string.IsNullOrEmpty(s)) return true;
    int i=0, j=s.Length-1;
    while(i<j)
    {
        while(i<j && !IsAlphnumeric(s[i])) i++;
        while(i<j && !IsAlphnumeric(s[j])) j--;
        if(i<j && s[i].ToString().ToLower()!=s[j].ToString().ToLower()) return false;
        i++;
        j--;
    }
    return true;
}

public bool IsAlphnumeric(char c)
{
    int A_val = (int)'A';
    int Z_val = (int)'Z';
    int _0_val = (int)'0';
    int _9_val = (int)'9';
    int a_val = (int)'a';
    int z_val = (int)'z';
    int val = (int)c;
    if((val>=A_val && val<=Z_val)
    ||(val>=a_val && val<=z_val)
    ||(val>=_0_val && val<= _9_val))
    {
        return true;
    }
    return false;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.