Java: Valid Palindrome

Thought Process

To determine if a string is a valid palindrome, we first preprocess the string by removing all non-alphanumeric characters and converting it to lowercase. This ensures the comparison is case-insensitive and ignores special characters. We then use a two-pointer approach to compare characters from the beginning and end of the string, moving towards the center. If all corresponding characters match, the string is a palindrome; otherwise, it is not. 

class Solution {

    public boolean isPalindrome(String s) {
      
        StringBuilder sb = new StringBuilder();
        String str = s.toLowerCase();
        for(int i=0;i<str.length();i++){

            char ch = str.charAt(i);
            if(Character.isDigit(ch) || Character.isLetter(ch))
                sb.append(ch);
        }
        String original = sb.toString();
        String reversed = sb.reverse().toString(); 
        // sb.reverse() reverses StringBuilder inplace.

        return original.equals(reversed);
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the string twice: once for preprocessing and once for comparison, making it linear in time complexity.

Space Complexity: O(n)

The algorithm uses additional space to store the preprocessed string, where n is the length of the input string.

Code copied!