Detect palindrome in string

Question

Given a string, write a function to determine if it is a palindrome, meaning it reads the same forwards and backwards. The function should return a boolean value: true if the string is a palindrome and false otherwise. Ignore spaces, punctuation, and capitalization when making this determination.

Codemia · Accepted Answer

To determine if a string is a palindrome, we need to check if it reads the same forwards and backwards, ignoring spaces, punctuation, and capitalization. The two-pointer technique is a suitable pattern for this problem because it allows us to compare characters from both ends of the string while moving towards the center. This approach efficiently reduces the number of comparisons needed by focusing only on relevant characters.

1. **Preprocessing the String**: First, we will preprocess the input string by removing all non-alphanumeric characters and converting it to lowercase. For example, for the input string `"A man, a plan, a canal: Panama"`, the preprocessed string will be `"amanaplanacanalpanama"`.
2. **Two-Pointer Technique**: We will initialize two pointers: one at the start of the preprocessed string and one at the end. We will compare the characters at these pointers. If they are equal, we move both pointers towards the center. If they are not equal, we immediately return `false`.
3. **Loop Until Pointers Meet**: We continue this process until the two pointers meet or cross each other. If we successfully compare all corresponding characters without finding a mismatch, we return `true`.

```python
import re

def is_palindrome(s: str) -> bool:
    # Preprocessing: Remove non-alphanumeric characters and convert to lowercase
    processed_str = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
    left, right = 0, len(processed_str) - 1

# Two-pointer comparison
    while left < right:
        if processed_str[left] != processed_str[right]:
            return False
        left += 1
        right -= 1
    return True
```

The time complexity of this approach is O(n), where n is the length of the input string. This is due to the need to preprocess the string and potentially compare all characters in the worst case. The space complexity is O(n) as well, because we create a new string to hold the processed characters. However, the space complexity can be optimized to O(1) if we use a two-pointer approach directly on the original string without creating a new one, but that would complicate handling non-alphanumeric characters.

1. **Empty String**: An empty string should return `true` since it is technically a palindrome.
2. **Single Character**: A single character (e.g., `"a"`) should also return `true`.
3. **Strings with Only Spaces/Punctuation**: Strings like `"   "` or `"!!!"` should return `true` because they can be considered empty after preprocessing.
4. **Mixed Case and Punctuation**: Inputs like `"No 'x' in Nixon"` should also return `true` after proper preprocessing.

Detect palindrome in string

Supabase

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Supabase Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string