Check if a string is a valid palindrome


A is a palindrome sequence of characters, that reads the same forward and backwards. If the string contains any uppercase letters, we need to make it lowecase and also remove any non-alphanumeric characters. Alphanumeric characters are only allowed which  include letters and numbers.

Example

String pal = "otto";  // The string is a palindrome as it reads 'otto' from forward and backwards

String nonPal = "baan"  // The string is not a palindrom as it read 'baan' from forward and 'naab' from backwards

We will check in string for the above properties and return true if the string is a palindrome else return false.

 

Approach

  1. initialize two pointers l and r to the beginning and end of the input string s, respectively.  
  2. While l is less than r, check the characters at l and r.  If the character at l is not an alphanumeric character, increment l to skip it.  
  3. If the character at r is not an alphanumeric character, decrement r to skip it.  
  4. If the characters at l and r are alphanumeric and are equal (ignoring case), increment l and decrement r.  
  5. If the characters at l and r are not equal (ignoring case), return false as the input string is not a palindrome.
  6.  If the loop completes without returning false, the input string is a palindrome, so return true.

 

Complexity

  • Time Complexity: O(n), where n is the size of the array
  • Space Complexity: O(1),  where n is the size of the array

 

Java Code
import java.util.*;

class ValidPalindrome {

    public boolean isPalindrome(String s) {

        int left = 0;
        int right = s.length() - 1;
        while (left < right) {

            if (!Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            } else if (!Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            } else if (Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right))) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ValidPalindrome sequence = new ValidPalindrome();
        String stringToCheck = "A man, a plan, a canal: Panama";
        System.out.println("Input string is: " + stringToCheck);
        System.out.println("Given String is Palindrome :"+ sequence.isPalindrome(stringToCheck));
    }

}

Output

Input string is: A man, a plan, a canal: Panama
Given String is Palindrome :true



Thanks for feedback.



Read More....
Check if two strings are anagram of each other
Count the occurrence of chars in a given string
Find duplicate chars in a String
First non-repeating character in String
Reverse a string