Noisy Palindrome Algorithm (Check Lowercase Palindrome Strings)

You are given a string s containing lowercase and uppercase alphabet characters as well as digits from “0” to “9”. Return whether s is a palindrome if we only consider the lowercase alphabet characters.

Constraints
0 ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = “a92bcbXa”
Output
True
Explanation
If we only consider the lowercase characters, then s is “abcba” which is a palindrome.

Example 2
Input
s = “abZ”
Output
False

Filter out Noisy Characters

We can filter out noisy characters such as uppercase or digits. Then we can validate the new string to see if it is a palindrome. For example, we can use two pointer algorithm to validate a palindrome string:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def solve(self, s):
        x = ""
        for i in s:
            if i >= 'a' and i <= 'z':
                x += i
        i, j = 0, len(x) - 1
        while i <= j:
            if x[i] != x[j]:
                return False
            i += 1
            j -= 1
        return True

class Solution:
    def solve(self, s):
        x = ""
        for i in s:
            if i >= 'a' and i <= 'z':
                x += i
        i, j = 0, len(x) - 1
        while i <= j:
            if x[i] != x[j]:
                return False
            i += 1
            j -= 1
        return True

Or even in Python, we can compare if its reversed version by using one-liner:

1
2
3
4
5
6
7

class Solution:
    def solve(self, s):
        x = ""
        for i in s:
            if i >= 'a' and i <= 'z':
                x += i
        return x[::-1] == x

class Solution:
    def solve(self, s):
        x = ""
        for i in s:
            if i >= 'a' and i <= 'z':
                x += i
        return x[::-1] == x

This algorithm takes O(N) time (two passes) and O(N) space as we need to store the constructed new string.

Two Pointer Algorithm to Validate a Noisy Palindrome String

In fact, we can skip non-lower-case letters on the fly. And still we can use the Two Pointer Algorithm. The following Python applies the two pointer algorithm by skipping noisy characters.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def solve(self, s):
        i, j = 0, len(s) - 1
        while i <= j:
            while (not s[i].islower()) and i < j:
                i += 1
            while (not s[j].islower()) and i < j:
                j -= 1
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

class Solution:
    def solve(self, s):
        i, j = 0, len(s) - 1
        while i <= j:
            while (not s[i].islower()) and i < j:
                i += 1
            while (not s[j].islower()) and i < j:
                j -= 1
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

The time complexity is O(N) – one pass, and the space complexity is O(1) constant.

See also: How to Break a Palindrome String by Replacing a Character?

–EOF (The Ultimate Computing & Technology Blog) —