Valid Palindrome - Practice Coding Problems

Valid Palindrome - Problem

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.

Input & Output

Example 1 — Classic Palindrome

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

› Output: true

💡 Note: After cleaning: "amanaplanacanalpanama" reads the same forwards and backwards

Example 2 — Not a Palindrome

$ Input: s = "race a car"

› Output: false

💡 Note: After cleaning: "raceacar" vs reverse "raceacar" - wait, let me recalculate: "raceacar" vs "raceacar" is same, but "race a car" becomes "raceacar" which is not "raceacar" reversed. Actually "raceacar" reversed is "raceacar" - this is wrong. Let me fix: "race a car" → "raceacar" → reverse is "raceacar". The issue is "race a car" cleans to "raceacar" but reversed would be "raceacar". Actually, "raceacar" backwards is "raceacar" which is the same. Let me think again: r-a-c-e-a-c-a-r backwards is r-a-c-a-e-c-a-r. So "raceacar" vs "racaecar" - not the same.

Example 3 — Empty After Cleaning

$ Input: s = " "

› Output: true

💡 Note: After removing non-alphanumeric: empty string, which is considered a palindrome

Constraints

1 ≤ s.length ≤ 2 * 10⁵
s consists only of printable ASCII characters.

Visualization

Tap to expand

Understanding the Visualization

Input

Original string with mixed characters

Process

Compare alphanumeric characters (case-insensitive)

Output

Boolean result: true if palindrome

Key Takeaway

🎯 Key Insight: Use two pointers to compare characters from both ends without creating extra strings

Asked in

M Meta 45 A Amazon 38 M Microsoft 32 A Apple 28

The key insight is to use two pointers from both ends, skipping non-alphanumeric characters and comparing valid characters in lowercase. The optimal two pointers approach avoids extra space while maintaining O(n) time complexity. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Clean and Reverse	O(n)	O(n)	Clean string first, then compare with its reverse
Two Pointers	O(n)	O(1)	Use two pointers from both ends, skip non-alphanumeric characters

Clean and Reverse — Algorithm Steps

Clean string: remove non-alphanumeric, convert to lowercase
Reverse the cleaned string
Compare original cleaned string with reversed version

Visualization

Tap to expand

Step-by-Step Walkthrough

Original

Input string with mixed characters

Clean

Extract alphanumeric and lowercase

Compare

Check if cleaned equals its reverse

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

bool solution(char* s) {
    int len = strlen(s);
    char cleaned[len + 1];
    int cleanedLen = 0;
    
    // Clean string: keep only alphanumeric and convert to lowercase
    for (int i = 0; i < len; i++) {
        if (isalnum(s[i])) {
            cleaned[cleanedLen++] = tolower(s[i]);
        }
    }
    cleaned[cleanedLen] = '\0';
    
    // Compare with reverse
    for (int i = 0; i < cleanedLen / 2; i++) {
        if (cleaned[i] != cleaned[cleanedLen - 1 - i]) {
            return false;
        }
    }
    return true;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to clean string + single pass to reverse

✓ Linear Growth

Space Complexity

O(n)

Extra string to store cleaned version

⚡ Linearithmic Space

296.8K Views

High Frequency

~15 min Avg. Time

8.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Clean and Reverse — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler