10.18 Check Palindrome by Filtering Non-Letters

10.18.1 Problem Metadata

10.18.2 Description

Given a string s, determine whether it is a palindrome after filtering out all non-letter characters and ignoring case. A palindrome reads the same backward as forward.

An empty string is considered a palindrome.

10.18.3 Examples

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After filtering and lowercasing: "amanaplanacanalpanama" is a palindrome

Input: s = "race a car"
Output: false
Explanation: After filtering and lowercasing: "raceacar" is not a palindrome

Input: s = ""
Output: true
Explanation: Empty string is considered a palindrome

10.18.4 Constraints

  • 0 <= s.length <= 10^5
  • s consists of printable ASCII characters

10.18.5 Solution - Two Pointers with Filtering

10.18.5.1 Walkthrough

Your solution uses a two-phase approach: first filter and normalize the string, then check if it’s a palindrome using the two-pointer technique.

Phase 1: Filtering and Normalization 1. Create a StringBuilder to collect only letter characters 2. Iterate through the input string, checking each character with Character.isLowerCase() or Character.isUpperCase() 3. If the character is a letter, append it to the StringBuilder 4. Convert the filtered string to lowercase for case-insensitive comparison 5. Handle the edge case: empty filtered string returns true (empty string is a palindrome)

Phase 2: Palindrome Check 1. Use two pointers starting at both ends of the filtered string 2. Compare characters at left pointer l and right pointer r 3. If characters don’t match, immediately return false 4. Move pointers toward the center (l++, r--) 5. If all comparisons succeed, return true

Example walkthrough with s = "A man, a plan, a canal: Panama":

Step 1: Filter non-letters
  Original: "A man, a plan, a canal: Panama"
  After filtering: "AmanaplanacanalPanama"
  After lowercasing: "amanaplanacanalpanama"

Step 2: Two-pointer palindrome check
  l=0, r=20: 'a' == 'a' ✓
  l=1, r=19: 'm' == 'm' ✓
  l=2, r=18: 'a' == 'a' ✓
  ...continues until l > r
  Result: true

Example walkthrough with s = "race a car":

Step 1: Filter non-letters
  Original: "race a car"
  After filtering: "raceacar"
  After lowercasing: "raceacar"

Step 2: Two-pointer palindrome check
  l=0, r=7: 'r' != 'r' ✓
  l=1, r=6: 'a' != 'a' ✓
  l=2, r=5: 'c' != 'c' ✓
  l=3, r=4: 'e' != 'a' ✗
  Result: false

10.18.5.2 Analysis

  • Time Complexity: O(n)
    • First pass to filter characters: O(n) where n is the length of the input string
    • Converting to lowercase: O(m) where m is the length of the filtered string (m ≤ n)
    • Two-pointer palindrome check: O(m/2) = O(m)
    • Total: O(n + m + m) = O(n) since m ≤ n
  • Space Complexity: O(n)
    • StringBuilder to store filtered characters: O(m) where m ≤ n
    • testStr stores the lowercase version: O(m)
    • chars array in palindrome check: O(m)
    • Total: O(n) in the worst case where all characters are letters

10.18.5.3 Implementation Steps

  1. Initialize a StringBuilder to collect valid letter characters
  2. Iterate through input string with toCharArray():
    • Use Character.isLowerCase(c) || Character.isUpperCase(c) to identify letters
    • Append valid letters to StringBuilder
  3. Convert the filtered string to lowercase using toString().toLowerCase()
  4. Handle edge case: if filtered string is empty, return true
  5. Call helper method isPalindrome with the filtered string:
    • Convert string to character array for O(1) access
    • Initialize two pointers: left pointer at 0, right pointer at chars.length - 1
    • While left pointer does not exceed right pointer, compare characters at both positions:
      • If mismatch, return false
      • Otherwise, increment left pointer and decrement right pointer
    • If loop completes, return true

10.18.5.4 Code - Java

class Result {

    /*
     * Complete the 'isAlphabeticPalindrome' function below.
     *
     * The function is expected to return a BOOLEAN.
     * The function accepts STRING code as parameter.
     */

    public static boolean isAlphabeticPalindrome(String code) {
        StringBuilder sb = new StringBuilder();
        
        for(char c : code.toCharArray()) {
            if(Character.isLowerCase(c) || Character.isUpperCase(c)) {
                sb.append(c);
            }
        }
        
        String testStr = sb.toString().toLowerCase();    
        
        if(testStr.isEmpty()) {
            return true;
        }           
        
        return isPailndrome(testStr);
    }
    
    private static boolean isPailndrome(String str) {        
        char[] chars = str.toCharArray();
        int l = 0, r = chars.length - 1;
        
        while(l <= r) {
            if(chars[l] != chars[r]) {
                return false;
            }
            l++;
            r--;
        }
        
        return true;
    }
    

}