#125

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Valid Palindrome

Check if a given string is a valid palindrome by using two-pointer scanning and invariant tracking techniques.

Problem Statement

A valid palindrome is a string that reads the same forward and backward when considering only alphanumeric characters. To determine if a given string is a palindrome, convert all uppercase characters to lowercase and remove any non-alphanumeric characters.

The task is to return true if the string is a palindrome, or false otherwise. For example, for the string "A man, a plan, a canal: Panama", the function should return true, while for "race a car", it should return false.

Examples

Example 1

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

Output: true

"amanaplanacanalpanama" is a palindrome.

Example 2

Input: s = "race a car"

Output: false

"raceacar" is not a palindrome.

Example 3

Input: s = " "

Output: true

s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Constraints

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

Solution Approach

Two-pointer scanning

Use two pointers, one starting at the beginning and one at the end of the string. Skip non-alphanumeric characters and compare the characters at both pointers. If they are equal, move both pointers towards the center.

Invariant tracking

Track the invariant that the characters at the left pointer must match those at the right pointer as we progress through the string. If any mismatch occurs, return false immediately.

Efficient handling of characters

Ensure case-insensitivity by converting characters to lowercase and skip non-alphanumeric characters efficiently using simple conditions, maintaining linear time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string. This is because we only traverse the string once with two pointers, making it efficient for large inputs. The space complexity is O(1), as we do not use extra space apart from the two pointers and character comparisons.

What Interviewers Usually Probe

Evaluate the candidate’s ability to implement two-pointer techniques.
Check if the candidate effectively handles edge cases such as empty strings or strings with non-alphanumeric characters.
Observe the candidate's ability to optimize both time and space for this problem.

Common Pitfalls or Variants

Common pitfalls

Forgetting to ignore non-alphanumeric characters, which can lead to incorrect results.
Not converting all characters to lowercase, causing mismatches between uppercase and lowercase letters.
Not handling the empty string or edge cases where the string is very short.

Follow-up variants

Palindromes with mixed case and special characters.
Strings with a large number of non-alphanumeric characters.
Edge case handling for strings of length 1 or 0.

FAQ

How do I check if a string is a valid palindrome?

You can check if a string is a valid palindrome by comparing characters from both ends using two pointers, skipping non-alphanumeric characters and ensuring case-insensitivity.

What is the time complexity of solving the Valid Palindrome problem?

The time complexity is O(n), where n is the length of the string, as we traverse the string once with two pointers.

What are some common mistakes when solving the Valid Palindrome problem?

Some common mistakes include not properly skipping non-alphanumeric characters, failing to convert characters to lowercase, and not handling edge cases like empty strings.

How do I handle non-alphanumeric characters in the Valid Palindrome problem?

Non-alphanumeric characters should be skipped during the comparison by checking each character and moving the pointers accordingly.

Can you explain the two-pointer technique for Valid Palindrome?

The two-pointer technique involves setting one pointer at the beginning and the other at the end of the string, comparing characters and moving towards the center, skipping non-alphanumeric characters and handling case insensitivity.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to the two ends of the string $s$, and then loop through the following process until $i \geq j$:

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            if not s[i].isalnum():
                i += 1
            elif not s[j].isalnum():
                j -= 1
            elif s[i].lower() != s[j].lower():
                return False
            else:
                i, j = i + 1, j - 1
        return True

Continue Practicing

#151 reverse words in a string #165 compare version numbers #28 find the index of the first occurrence in a string