Valid Palindrome

Problem Link

125. Valid Palindrome – LeetCode

Problem Statement

A palindrome is a string that reads the same forward and backward.

You are given a string s. Return true if it is a valid palindrome after:

• Converting all uppercase letters to lowercase

• Removing all non-alphanumeric characters

Alphanumeric characters include both letters and numbers.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: s = " "
Output: true
Explanation: The cleaned string is "", which is a palindrome by definition.

Constraints

• 1 <= s.length <= 2 * 10⁵

• s contains only printable ASCII characters

Intuition

To determine whether a string is a palindrome:

• We must ignore cases (uppercase vs lowercase) and non-alphanumeric characters

• After cleanup, check if the cleaned string equals its reverse

We can do this efficiently using two pointers or recursive character comparison.

Approach

1. Create a new string with:

   • Only alphanumeric characters

   • All characters converted to lowercase

2. Use a recursive two-pointer check (start, end) to compare the characters from both ends.

3. If all matching → return true, else return false.

Java Code

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            if (isAlphaNum(s.charAt(i))) {
                char ch = Character.toLowerCase(s.charAt(i));
                sb.append(ch);
            }
        }

        return checkPal(sb.toString(), 0, sb.length() - 1);
    }

    private boolean checkPal(String str, int s, int e) {
        if (s >= e) return true;
        if (str.charAt(s) != str.charAt(e)) return false;
        return checkPal(str, s + 1, e - 1);
    }

    private boolean isAlphaNum(char ch) {
        return (ch >= 'a' && ch <= 'z') ||
               (ch >= 'A' && ch <= 'Z') ||
               (ch >= '0' && ch <= '9');
    }
}

Time and Space Complexity

Dry Run

Input:

s = "A man, a plan, a canal: Panama"

Steps:

• After filtering and lowercase: s_cleaned = "amanaplanacanalpanama"

• Compare: s_cleaned[0] == s_cleaned[20], s_cleaned[1] == s_cleaned[19] ... and so on

• All match → return true

Output:

true

Alternate Approaches

Two-pointer (iterative): Avoids creating a new string → even more memory-efficient
Stack-based: Not recommended unless palindromes in nested structure

Conclusion

This problem emphasizes:

• Data cleaning: Removing noise (non-alphanumeric characters)

• String normalization: Lowercasing

• Palindrome checking: Recursion or two-pointer

The core takeaway: always preprocess input carefully in string manipulation problems.

Intuition - Recursion

We need to check whether the string reads the same forwards and backwards, ignoring non-alphanumeric characters and case.

We will clean the string to remove all non-alphanumeric characters and convert it to lowercase, then use recursion with two pointers (left and right) to check for palindrome.

Induction – Base Case – Hypothesis Method (Recursive Structure)

Function Signature

boolean isPalindromeHelper(String s, int left, int right)

Base Case

If left >= right, it means we have checked all characters and found them matching. So, return true.

Hypothesis

Assume that the substring s[left + 1, ..., right - 1] is a palindrome.

Induction Step

Check:

• If s.charAt(left) != s.charAt(right) → return false.

• Else → recursively check for the smaller substring: isPalindromeHelper(s, left + 1, right - 1).

Approach

1. Preprocess the string:

   • Remove all non-alphanumeric characters.

   • Convert all characters to lowercase.

2. Use recursive function with two pointers left and right.

3. Use Induction-Base-Hypothesis method to verify palindrome.

Code (Java)

class Solution {
    public boolean isPalindrome(String s) {
        // Step 1: Preprocess the string
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                sb.append(Character.toLowerCase(c));
            }
        }
        String cleaned = sb.toString();
        return isPalindromeHelper(cleaned, 0, cleaned.length() - 1);
    }

    // Recursive palindrome check using Induction-Base-Hypothesis
    private boolean isPalindromeHelper(String s, int left, int right) {
        // Base case
        if (left >= right) return true;

        // Induction
        if (s.charAt(left) != s.charAt(right)) return false;

        // Hypothesis
        return isPalindromeHelper(s, left + 1, right - 1);
    }
}

Time and Space Complexity

• Time Complexity: O(n)

  • O(n) for cleaning the string

  • O(n) for recursive checks

• Space Complexity:

  • O(n) for cleaned string

  • O(n) recursive call stack in worst case

Dry Run

Input:

s = "A man, a plan, a canal: Panama"
Cleaned string = "amanaplanacanalpanama"

• isPalindromeHelper("amanaplanacanalpanama", 0, 20)

• a == a → recurse

• m == m → recurse

• a == a → recurse

• ...

• Final call: left >= right → return true

Conclusion

This is a textbook application of recursion using the Induction – Base – Hypothesis approach. It emphasizes how recursive thought mimics looped pair-checking and is a great exercise to build foundational recursive thinking.

Let me know if you want the iterative version or more recursion problems.