Data Structures & Algorithms in Java – Strings – Valid Palindrome

Problem:

Given a string with both alphanumeric and non alphanumeric characters , find if it is a valid palindrome ignoring the non alphanumeric characters and converting the upper case letters to lower case letters

For example,

The input:

“A man , a plan, a canal: Panama” is a valid palindrome after you remove the special characters and convert remaining characters to lower case (amanaplanacanalpanama)

The input: “music is great” is invalid.

Try out the solution here:

https://leetcode.com/problems/valid-palindrome/

Solution:

Hint:

• Use two pointers one from the start and another from the end.

The easiest solution to this problem is to remove the non alphanumeric characters from the original string using string.replaceAll(“[^A-Za-z0-9]”,””) , then reverse the string using string.reverse() method and compare if both are equal.

If you are given the constraint that you can’t use reverse() method in java , then you have to go with two pointer approach.

Here is the algorithm for the same:

ALGORITHM:

STEP 1: Convert the given string to a character array

STEP 2: Declare two pointers left and right pointing to the left and right of the string.

STEP 3: If the string is of length 1 return true

STEP 4: Until left pointer is less than right pointer , for each character pointed by the pointers

STEP 4a: Check if they are non alphanumeric , then if it is left pointer keep incrementing , if it is right pointer keep decrementing until an alphanumeric character is reached

STEP 4b: For alphanumeric character , convert to lower case and check if the characters are equal , if not return false immediately

STEP 5: Return true

Code:

class Solution {
    public boolean isPalindrome(String s) {
        
        
        char[] input = s.toCharArray();
        
        int left = 0;
        
        int right = s.length() -1;
        
        
        if(right ==0) return true;
        
        
        while(left <= right){
            
            int l = Integer.valueOf(input[left]);
            
            int r = Integer.valueOf(input[right]);
        
            
            while(!(l >= 65 && l <= 90 || l >= 97 && l <=122 || l >=48 && l <=57) && left < right){
                
                
                left++;
                l = Integer.valueOf(input[left]);
            }
            
              while(!(r >= 65 && r <= 90 || r >= 97 && r <=122 || r >=48 && r <=57) && right > left){
                
                right--;
                  r = Integer.valueOf(input[right]);
            }
            
            
            if(Character.toLowerCase(input[left]) == Character.toLowerCase(input[right])){
                
            
                left++;
                
                right--;
            }else{
                
                return false;
            }
            
         
        }
        
        
        
        
        return true;
    }
}

Time complexity is O(n/2) which can be considered as O(n) and the space complexity is O(n) to store the character array representing the input.

That’s it!