Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Palindrome Definition

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
3
4

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.

Note

Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

Similar Problem

Check if given string is palindrome or not

Solution

From start and end loop though the string, i.e., char array. If it is not alpha or number, increase or decrease pointers. Compare the alpha and numeric characters. The solution below is pretty straightforward.

We have seen similar problem - Check if given string is palindrome or not.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Removing non-alphanumeric characters and check the reversed

Code

1
2
3
4
5
6
7
8
9

class Solution {
    public boolean isPalindrome(String s) {
        // Preprocess the string using regex: remove non-alphanumeric characters and convert to lowercase
        String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

        // Compare the cleaned string with its reverse
        return cleaned.equals(new StringBuilder(cleaned).reverse().toString());
    }
}
1
2
3
4
5
6
7

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Preprocess the string using regex
        cleaned = re.sub(r"[^a-zA-Z0-9]", "", s).lower()  # Remove non-alphanumeric characters and convert to lowercase

        # Compare the cleaned string with its reverse
        return cleaned == cleaned[::-1]

Method 1 - Removing non-alphanumeric chars and Using 2 Pointers

Some interviewers may not allow above.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public static boolean isValidPalindrome(String s) {

	s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

	for (int i = 0; i<s.length(); i++) {
		if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
			return false;
		}
	}

	return true;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Using 2 pointers after lowercasing the string

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
27
28
29
30
31
32
33

public boolean isPalindrome2(String s) {
	if (s == null || s.isEmpty()) {
		return true;
	}
	s = s.toLowerCase();
	for (int i = 0, j = s.length() - 1; i < j; ) {
		char leftChar = s.charAt(i);
		char rightChar = s.charAt(j);
		if (!isAlphaNum(leftChar)) {
			i++;
			continue;
		}
		if (!isAlphaNum(rightChar)) {
			j--;
			continue;
		}
		if (leftChar != rightChar) {
			return false;
		}
		i++;
		j--;
	}
	return true;
}

public boolean isAlphaNum(char a) {
	if ((a >= 'a' && a<= 'z') || 
		(a >= 'A' && a<= 'Z') || 
		(a >= '0' && a<= '9')) {
		return true;
	} 
	return false;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Using 2 pointers - No shortcuts

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
27
28
29
30
31
32
33
34

public boolean isPalindrome(String s) {
	if (s == null) {
		return true;
	}
	if (s.length()<2) {
		return true;
	}
	int n = s.length();
	int i = 0; // left pointer
	int j = n - 1; // right pointer

	while (i<j) {
		// note upper bound is r and not n
		// this improves time complexity a bit
		while (i < j && !isAlphaNum(s.charAt(i))) {
			i++;
		}
	
		while (j > i && !isAlphaNum(s.charAt(j))) {
			j--;
		}

		if (i >= j)
			break;

		if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
			return false;
		}

		i++;
		j--;
	}
	return true;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 4 - Using Stack

This solution removes the special characters first.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public boolean isPalindrome(String s) {
	// a shortcut
	s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

	int len = s.length();

	if (len < 2) {
		return true;
	}

	Stack<Character> stack = new Stack<Character>();

	int index = 0;

	while (index < len / 2) {
		stack.push(s.charAt(index));
		index++;
	}

	if (len % 2 == 1) {
		index++;
	}

	while (index < len) {
		if (stack.empty()) {
			return false;
		}
			
		char temp = stack.pop();

		if (s.charAt(index) != temp) {
			return false;
		} else {
			index++;
		}

	}

	return true;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)