Filtered Palindrome

Overview

The goal of this problem is to determine if a sequence of characters is a palindrome, but with a twist: we must completely ignore specific characters defined in an ignoreArray. A sequence is a palindrome if it reads the same forward and backward.

The problem essentially requires two logical steps:

1. Filtering: Determining which characters in inputArray are "valid" (not in ignoreArray).
2. Validation: Checking if the resulting sequence of valid characters is symmetric.

Brute Force

The simplest way to solve this is to explicitly create a new list containing only the characters from inputArray that do not appear in ignoreArray. Once we have this "cleaned" list, we can compare it to its reverse to see if they are identical.

To make the lookups efficient even in a brute force approach, we should convert the ignoreArray into a set. Checking if an item exists in a set takes $O(1)$ on average, whereas checking a list takes $O(K)$.

def isFilteredPalindrome(ignoreArray: list[str], inputArray: list[str]) -> bool:
    # Convert ignore list to a set for O(1) lookups
    ignore_set = set(ignoreArray)
    
    # Filter the input array to remove ignored characters
    filtered_chars = [char for char in inputArray if char not in ignore_set]
    
    # A list is a palindrome if it equals its reverse
    return filtered_chars == filtered_chars[::-1]

Time complexity: O(N + K) — We iterate through ignoreArray once to build the set (size K) and inputArray once to filter (size N). Space complexity: O(N + K) — We store K characters in a set and up to N characters in the new filtered list.

Optimal / Best Approach

The problem note mentions that inputArray might be significantly larger than ignoreArray and asks for efficiency in terms of space complexity. We can achieve O(1) auxiliary space (excluding the set for ignored characters) by using a Two-Pointer Technique.

Instead of creating a new filtered list, we place one pointer (left) at the start of inputArray and another (right) at the end. We move these pointers toward the center, skipping any characters that are in the ignore_set. At each valid step, we compare the characters at left and right. If they don't match, it's not a palindrome.

def isFilteredPalindrome(ignoreArray: list[str], inputArray: list[str]) -> bool:
    ignore_set = set(ignoreArray)
    left = 0
    right = len(inputArray) - 1
    
    while left < right:
        # Move left pointer if current char is in ignore_set
        if inputArray[left] in ignore_set:
            left += 1
            continue
            
        # Move right pointer if current char is in ignore_set
        if inputArray[right] in ignore_set:
            right -= 1
            continue
        
        # Both pointers are now on valid characters; compare them
        if inputArray[left] != inputArray[right]:
            return False
        
        # Move both pointers inward after a successful match
        left += 1
        right -= 1
        
    return True

Time complexity: O(N + K) — We still visit each character in inputArray at most once and ignoreArray once. Space complexity: O(K) — We store the ignoreArray in a set for fast lookup, but we no longer create a new filtered version of inputArray.

Edge Cases

• Empty Result: If all characters in inputArray are present in ignoreArray, the sequence is effectively empty. An empty sequence is symmetric and should return True.
• Single Character: After filtering, if only one character remains, it is a palindrome.
• No Matches: If no characters are in the ignoreArray, the function behaves like a standard palindrome checker.

Fast