Problem: Valid Palindrome
Problem Statement:
Given a string s
, determine if it is a valid palindrome, considering only alphanumeric characters and ignoring case. A palindrome is a string that reads the same forward and backward.
Note:
- A valid palindrome ignores spaces, punctuation, and case sensitivity.
- Only alphanumeric characters are considered for palindrome checking.
Example 1:
Input:
s = "A man, a plan, a canal, Panama"
Output:
true
Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes: "amanaplanacanalpanama"
, which is a palindrome.
Example 2:
Input:
s = "race a car"
Output:
false
Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes: "raceacar"
, which is not a palindrome.
Constraints:
1 <= s.length <= 2 * 10^5
s
consists only of printable ASCII characters.
Approach:
We can use a two-pointer technique to check whether a string is a valid palindrome:
- Use two pointers:
- One pointer starts from the beginning of the string.
- Another pointer starts from the end of the string.
- Move both pointers toward the center of the string.
- At each step, check if the characters at both pointers are equal:
- If they are not equal, return
false
. - If they are equal, continue checking the next characters.
- If they are not equal, return
- Ignore non-alphanumeric characters and check for case-insensitivity.
- If all the characters match while considering the above rules, return
true
.
Time Complexity:
- Time Complexity:
O(n)
, wheren
is the length of the string. We are only traversing the string once. - Space Complexity:
O(1)
for the two-pointer approach, as we do not use any additional space beyond a few pointers.
Code Implementations in Multiple Languages:
1. C
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int isPalindrome(char *s) {
int left = 0, right = strlen(s) - 1;
while (left < right) {
// Move left pointer to the next alphanumeric character
while (left < right && !isalnum(s[left])) {
left++;
}
// Move right pointer to the previous alphanumeric character
while (left < right && !isalnum(s[right])) {
right--;
}
// Compare characters case-insensitively
if (tolower(s[left]) != tolower(s[right])) {
return 0; // Not a palindrome
}
left++;
right--;
}
return 1; // Is a palindrome
}
int main() {
char s[] = "A man, a plan, a canal, Panama";
if (isPalindrome(s)) {
printf("true\n");
} else {
printf("false\n");
}
return 0;
}
2. C++
#include <iostream>
#include <cctype>
#include <string>
using namespace std;
bool isPalindrome(string s) {
int left = 0, right = s.length() - 1;
while (left < right) {
// Move left pointer to the next alphanumeric character
while (left < right && !isalnum(s[left])) {
left++;
}
// Move right pointer to the previous alphanumeric character
while (left < right && !isalnum(s[right])) {
right--;
}
// Compare characters case-insensitively
if (tolower(s[left]) != tolower(s[right])) {
return false; // Not a palindrome
}
left++;
right--;
}
return true; // Is a palindrome
}
int main() {
string s = "A man, a plan, a canal, Panama";
cout << (isPalindrome(s) ? "true" : "false") << endl;
return 0;
}
3. Java
public class Main {
public static boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
// Move left pointer to the next alphanumeric character
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
// Move right pointer to the previous alphanumeric character
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
// Compare characters case-insensitively
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false; // Not a palindrome
}
left++;
right--;
}
return true; // Is a palindrome
}
public static void main(String[] args) {
String s = "A man, a plan, a canal, Panama";
System.out.println(isPalindrome(s));
}
}
4. Python
def isPalindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
# Move left pointer to the next alphanumeric character
while left < right and not s[left].isalnum():
left += 1
# Move right pointer to the previous alphanumeric character
while left < right and not s[right].isalnum():
right -= 1
# Compare characters case-insensitively
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
# Test case
s = "A man, a plan, a canal, Panama"
print(isPalindrome(s)) # Output: True
5. C#
using System;
class Program {
public static bool IsPalindrome(string s) {
int left = 0, right = s.Length - 1;
while (left < right) {
// Move left pointer to the next alphanumeric character
while (left < right && !Char.IsLetterOrDigit(s[left])) {
left++;
}
// Move right pointer to the previous alphanumeric character
while (left < right && !Char.IsLetterOrDigit(s[right])) {
right--;
}
// Compare characters case-insensitively
if (Char.ToLower(s[left]) != Char.ToLower(s[right])) {
return false;
}
left++;
right--;
}
return true;
}
static void Main() {
string s = "A man, a plan, a canal, Panama";
Console.WriteLine(IsPalindrome(s)); // Output: True
}
}
6. JavaScript
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
// Move left pointer to the next alphanumeric character
while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
left++;
}
// Move right pointer to the previous alphanumeric character
while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
right--;
}
// Compare characters case-insensitively
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left++;
right--;
}
return true;
}
// Test case
const s = "A man, a plan, a canal, Panama";
console.log(isPalindrome(s)); // Output: true
Summary:
- Approach: Use two pointers to check characters from both ends of the string, ignoring non-alphanumeric characters and considering case insensitivity.
- Time Complexity: O(n)O(n)O(n), where nnn is the length of the string.
- Space Complexity: O(1)O(1)O(1), as the space used is constant, with only a few pointers.