Leetcode 125: Valid Palindrome

Input: The input is a string s that consists of printable ASCII characters.

Example: Input: s = 'Was it a car or a cat I saw?'

Constraints:

• 1 <= s.length <= 2 * 10^5

• s consists only of printable ASCII characters

Output: The output is a boolean value, true if the string is a palindrome, otherwise false.

Example: Output: true

Constraints:

• The string is considered a palindrome if it reads the same when ignoring non-alphanumeric characters and case differences.

Goal: The goal is to check if the given string is a palindrome after ignoring non-alphanumeric characters and converting all letters to lowercase.

Steps:

• Initialize two pointers, one at the start (i = 0) and one at the end (j = s.length() - 1).

• While the two pointers have not crossed each other, check the characters at both pointers.

• If the character at pointer i is not alphanumeric, move i forward.

• If the character at pointer j is not alphanumeric, move j backward.

• If the characters at i and j are equal (ignoring case), move both pointers inward.

• If any character comparison fails, return false.

• If the loop completes without finding any mismatches, return true.

Goal: The constraints ensure that the input string will have at least one character and no more than 200,000 characters.

Steps:

• 1 <= s.length <= 2 * 10^5

• s consists only of printable ASCII characters

Assumptions:

• The string will always contain at least one character.

• We will only work with printable ASCII characters.

• Input: Input: s = 'Was it a car or a cat I saw?'

• Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes 'wasitacaroracatisaw', which is the same forward and backward, so the answer is true.

• Input: Input: s = 'race a car'

• Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes 'raceacar', which is not the same forward and backward, so the answer is false.

• Input: Input: s = ' '

• Explanation: After removing non-alphanumeric characters, the string becomes an empty string, which is considered a palindrome, so the answer is true.

Approach: We use two pointers to compare the characters of the string from both ends, ignoring non-alphanumeric characters and case differences. The process continues until we check all characters or find a mismatch.

Observations:

• Using two pointers is an efficient way to check for palindrome properties.

• We need to account for both case insensitivity and ignoring non-alphanumeric characters.

Steps:

• Initialize two pointers: one starting from the beginning of the string and the other from the end.

• While the left pointer is less than or equal to the right pointer, check the characters.

• Skip non-alphanumeric characters by moving the pointers inward if necessary.

• Compare the characters at both pointers after converting them to lowercase.

• If they don't match, return false. If they match, continue the process.

• If no mismatches are found, return true.

Empty Inputs:

• The input can be an empty string, which is considered a palindrome.

Large Inputs:

• The solution must handle inputs with up to 200,000 characters efficiently.

Special Values:

• Strings with only non-alphanumeric characters should be considered palindromes as they become empty after removal.

Constraints:

• Ensure that the input string is within the specified length.

bool isPalindrome(string s) {
    int i = 0, j = s.size() - 1;
    while(i <= j) {
        if(!isalnum(s[i])) {
            i++; continue;
        }
        if(!isalnum(s[j])) {
            j--; continue;
        }
        if(tolower(s[i]) == tolower(s[j])) {
            i++, j--;
        } else return false;
    }
    return true;
}

1 : Function Declaration

bool isPalindrome(string s) {

Declare a function to determine if the input string is a valid palindrome.

2 : Variable Initialization

    int i = 0, j = s.size() - 1;

Initialize two pointers: `i` at the start of the string and `j` at the end.

3 : Loop Iteration

    while(i <= j) {

Start a loop to check characters from both ends of the string.

4 : Conditional Check

        if(!isalnum(s[i])) {

Check if the current character at the start pointer is non-alphanumeric.

5 : Pointer Update

            i++; continue;

Move the start pointer forward and skip the current character if it's non-alphanumeric.

6 : Conditional Check

        if(!isalnum(s[j])) {

Check if the current character at the end pointer is non-alphanumeric.

7 : Pointer Update

            j--; continue;

Move the end pointer backward and skip the current character if it's non-alphanumeric.

8 : Comparison

        if(tolower(s[i]) == tolower(s[j])) {

Compare the lowercase versions of the characters at both pointers.

9 : Pointer Update

            i++, j--;

Move both pointers closer to the center if the characters match.

10 : Return Statement

        } else return false;

Return false if the characters do not match.

11 : Return Statement

    return true;

Return true if all character pairs matched, confirming the string is a palindrome.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we process each character of the string at most once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we only store a few variables (pointers) regardless of the input size.

Leetcode 125: Valid Palindrome

Solution to LeetCode 125: Valid Palindrome Problem

Explore →