Skip to main content

Valid Palindrome Solution

Problem Description​

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.

Examples​

Example 1:

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

Example 2:

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

Constraints​

  • 1≤s.length≤2×1051 \leq s.length \leq 2 \times 105

Solution for Valid Palindrome Problem​

Approach 1: Brute Force​

Intuition​

The brute force approach involves stripping non-alphanumeric characters from the string and then checking if the resulting string is a palindrome by comparing it with its reverse.

Implementation​

Code in Different Languages​

// JAVA

class Solution {
    public boolean isPalindrome(String s) {
        String str = s.toLowerCase();
        str = str.replaceAll("\\s",""); // remove all space in string
        str = str.replaceAll("[^a-z0-9]",""); // remove all non-alphanumerical
        int i=0,j=str.length()-1;
        while(i<j){
            char ch = str.charAt(i);
            char ch1 = str.charAt(j);
            if(ch==ch1){
                i++;
                j--;
            }
            else return false;
        }
        return true;
    }
 } 

//Java-script

   var isPalindrome = function(s){
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (!isAlphaNumeric(s[left]))
            left++;
        else if (!isAlphaNumeric(s[right]))
            right--;
        else if (s[left].toLowerCase() !== s[right].toLowerCase())
            return false;
        else {
            left++;
            right--;
        }
    }
    return true;
}

function isAlphaNumeric(char) {
    const code = char.charCodeAt(0);
    return (code >= 48 && code <= 57) || (code >= 65 && code <= 90) || (code >= 97 && code <= 122);
}
//python

 def is_palindrome(s: str) -> bool:
   if not s:
       return True
   cleaned_s = ''.join(ch.lower() for ch in s if ch.isalnum())
   return cleaned_s == cleaned_s[::-1]

   input_str = "A man, a plan, a canal: Panama"
   output = is_palindrome(input_str)

   print("Input:", input_str)
   print("Output:", output)

//java
 class Solution {
     public boolean isPalindrome(String s) {
         if (s == null || s.isEmpty()) {
             return true;
         }
         
         String cleanedS = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
         return cleanedS.equals(new StringBuilder(cleanedS).reverse().toString());
     }
 }
//cpp

 class Solution {
 public:
     bool isPalindrome(string s) {
         if (s.empty()) {
             return true;
         }
         
         string cleanedS;
         for (char ch : s) {
             if (isalnum(ch)) {
                 cleanedS += tolower(ch);
             }
         }
         
         string reversedS = cleanedS;
         reverse(reversedS.begin(), reversedS.end());
         
         return cleanedS == reversedS;
     }
 };

Complexity Analysis​

  • Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
  • Space Complexity: O(n), where n is the length of the input string. We create a new string to store the cleaned version of the input.

References​