Valid Palindrome In C,CPP,JAVA,PYTHON,C#,JS

Spread the love
Close-up of HTML code highlighted in vibrant colors on a computer monitor.

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:

  1. Use two pointers:
    • One pointer starts from the beginning of the string.
    • Another pointer starts from the end of the string.
  2. Move both pointers toward the center of the string.
  3. 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.
  4. Ignore non-alphanumeric characters and check for case-insensitivity.
  5. If all the characters match while considering the above rules, return true.

Time Complexity:

  • Time Complexity: O(n), where n 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.