Valid Palindrome - From String Manipulation to O(1) Space Two-Pointers (Java)

Today we're back to string manipulation with a very common and foundational problem: "Valid Palindrome" (LeetCode #125).

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. The twist here is that we need to consider only alphanumeric characters and ignore case. I'll show you two distinct approaches: a straightforward string manipulation method and an optimized solution using the Two-Pointer pattern for O(1) additional space. Let's dive in!

---

Understanding the Problem:

We are given a string s. Our task is to return true if it is a palindrome, and false otherwise.

The key rules for determining a palindrome in this problem are:

1. Case-Insensitive: 'A' should be treated the same as 'a'.

2. Ignore Non-Alphanumeric Characters: Only letters (a-z, A-Z) and digits (0-9) count. All other characters (spaces, punctuation, symbols) should be ignored.

Examples:

• Input: s = "Was it a car or a cat I saw?"

  • Output: true

  • Explanation: After filtering and converting to lowercase, it becomes "wasitacaroracatisaw", which reads the same forwards and backwards.

• Input: s = "tab a cat"

  • Output: false

  • Explanation: After filtering, it becomes "tabacat", which is not a palindrome.

---

Approach 1: String Preprocessing and Reversal (Straightforward Approach)

My initial thought for this problem is to make the string "clean" first, so that a direct comparison can be made. This involves two main steps:

1. Clean the String:

   • Remove all non-alphanumeric characters. Regular expressions are very handy for this.

   • Convert the entire string to lowercase to handle the case-insensitivity requirement.

   • In Java, replaceAll("[^a-zA-Z0-9]","") (or [^a-z0-9] after converting to lowercase) and toLowerCase() are perfect tools.

2. Check for Palindrome:

   • Create a reversed version of the cleaned string. StringBuilder is efficient for this.

   • Compare the original cleaned string with its reversed version. If they are equal, it's a palindrome.

This approach is easy to understand and implement, making it a good first pass.

Java Code Implementation (Approach 1 - String Preprocessing & Reversal):

class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
        StringBuilder sb = new StringBuilder(s);
        if(s.equals(sb.reverse().toString()))
            return true;
        else
            return false;
    }
}

Time and Space Complexity Analysis (Approach 1):

• Time Complexity: O(N)

  • replaceAll(): This operation can take O(N) time, where N is the length of the string, as it might iterate through the string.

  • toLowerCase(): Also takes O(N) time.

  • StringBuilder construction: O(N) time.

  • StringBuilder.reverse(): O(N) time.

  • toString(): O(N) time.

  • equals(): O(N) time in the worst case.

  • Overall, the dominant operations are linear, resulting in O(N) time complexity.

• Space Complexity: O(N)

  • replaceAll() might create new intermediate strings.

  • toLowerCase() creates a new string.

  • StringBuilder creates a new character array of size O(N).

  • sb.reverse().toString() creates another new string.

  • Therefore, the space complexity is O(N) due to the creation of multiple new string/StringBuilder objects.

---

Approach 2: Two-Pointers (Optimal O(1) Space Solution)

While the first approach is easy to understand, the creation of multiple new string objects can be inefficient in terms of space. The problem's requirement to compare characters from both ends (forward and backward) immediately suggests the Two-Pointer pattern, which can be implemented in-place without extra space.

Here's the thought process for this optimized approach:

1. Initialize Pointers:

   • Set a left pointer (i) at the beginning of the string (index 0).

   • Set a right pointer (j) at the end of the string (index s.length() - 1).

2. Iterate and Validate:

   • Loop as long as left is less than right (i < j).

   • Skip Non-Alphanumeric Characters:

     • Move the left pointer forward (i++) until it points to an alphanumeric character.

     • Move the right pointer backward (j--) until it points to an alphanumeric character.

     • Important: Ensure i and j don't cross during these skips. If i becomes >= j after skipping, it means we've processed all relevant characters, and the string is a palindrome.

   • Compare Alphanumeric Characters:

     • Once both i and j point to alphanumeric characters, convert both characters to lowercase using Character.toLowerCase().

     • Compare these lowercase characters. If they are not equal, the string is not a palindrome, so return false.

   • Advance Pointers: If the characters match, move both pointers inwards (i++, j--) to check the next pair.

3. Return True: If the loop completes without finding any mismatch, it means the string is a valid palindrome, so return true.

This approach processes the string in a single pass without creating any new string objects, making it very space-efficient.

Java Code Implementation (Approach 2 - Two-Pointers):

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int i = 0;
        int j = s.length()-1;
        while(i<j){
            while(i<n && !Character.isLetterOrDigit(s.charAt(i))){
                i++;
            }
            while(j>=0 && !Character.isLetterOrDigit(s.charAt(j))){
                j--;
            }
            if(i>j){
                break;
            }
            System.out.print(s.charAt(i) + " " + s.charAt(j));
            if(Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j))){
                return false;
            }
            i++;j--;
        }
        return true;
    }
}

Time and Space Complexity Analysis (Approach 2):

• Time Complexity: O(N)

  • In the worst case, both pointers traverse the entire string once. The inner while loops simply advance the pointers, effectively doing constant work per character (on average).

  • Each Character.isLetterOrDigit() and Character.toLowerCase() call is constant time.

  • Therefore, the total time complexity is O(N).

• Space Complexity: O(1)

  • We only use a few constant-space integer variables (n, i, j).

  • No auxiliary data structures are created whose size depends on the input N.

  • This makes it a highly space-efficient solution, fulfilling the typical "O(1) additional space" optimization requirement.