Problem Overview

  • We are given a string s.
  • The string consists of all printable ASCII characters.
  • Goal is to check if the string is a palindrome — but first we need to remove non-alphanumeric characters, then check.

A palindrome is a word or sentence if that reads the same backwards as forewords

LeetCode - Valid Palindrome

Example

1
2
3
4
5
6
7

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Visual explanation of strings are palindrome or not

Brute Force

Intuition

  • First, create a new string by removing all characters except a-z, A-Z, and 0-9.
  • Convert characters to lowercase to ignore case differences.
  • Then copy the output string and reverse it.
  • Compare each character — if any character is different, the string is not a palindrome.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    bool isPalindrome(string s) {

        string temp;

        for (auto it : s) {
            if ((it >= 'A' && it <= 'Z') ||
                (it >= 'a' && it <= 'z') ||
                (it >= '0' && it <= '9')) {
                temp += tolower(it);
            }
        }

        string rev = temp;
        reverse(rev.begin(), rev.end());

        int n = rev.size();
        for (int i = 0; i < n; i++) {
            if (rev[i] != temp[i])
                return false;
        }

        return true;
    }
};

Time and Space Complexity

  • Time → O(n)
  • Space → O(n) — extra temp and rev strings of size n

Optimization

Intuition

  • On observation, if the string is a palindrome, both halves must mirror of each other.
  • Instead of using another string and reversing it, we can use a two pointer approach.
  • Left pointer starts from 0 and right pointer from n-1.
  • If characters at left and right are the same, move both inward.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    bool isPalindrome(string s) {

        string clean;

        for (auto it : s) {
            if ((it >= 'A' && it <= 'Z') ||
                (it >= 'a' && it <= 'z') ||
                (it >= '0' && it <= '9')) {
                clean += tolower(it);
            }
        }

        int n = clean.size();
        int l = 0, r = n - 1;

        while (l <= r) {
            if (clean[l] != clean[r]) return false;
            l++;
            r--;
        }

        return true;
    }
};

Time and Space Complexity

  • Time → O(n)
  • Space → O(n) — still using the clean string of size n

Further Optimization

Intuition

  • Instead of creating a new string, we can directly operate on the original string s.
  • Use two pointers starting from 0 and n-1.
  • Skip characters that are not alphanumeric.
  • Once both pointers point to valid characters, compare them.
  • If they match, move both pointers inward.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool isPalindrome(string s) {

        int l = 0, r = s.size() - 1;

        while (l < r) {

            while (l < r && !isalnum(s[l])) l++;
            while (l < r && !isalnum(s[r])) r--;

            if (tolower(s[l]) != tolower(s[r]))
                return false;

            l++;
            r--;
        }

        return true;
    }
};

Time and Space Complexity

  • Time → O(n)
  • Space → O(1)

Key Takeaways

  • Small observations can lead to big optimizations.
  • Small improvements can make the algorithm more efficient.