algoadvance

Leetcode 125. Valid Palindrome

Problem Statement:

The given problem is from LeetCode, and it’s numbered 125. The problem statement is as follows:

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example:

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

• Output: true

• Input: s = "race a car"
• Output: false

Clarifying Questions:

1. Can the input string be empty?
   • Yes, an empty string or a string with only non-alphanumeric characters should be considered a valid palindrome.
2. Is the case of the characters important when checking for a palindrome?
   • No, the case is not important. We should treat ‘A’ and ‘a’ as the same character.
3. Should spaces, punctuation, and other non-alphanumeric characters be ignored?
   • Yes, we should ignore all non-alphanumeric characters.

Strategy:

1. Clean the string:
   • Iterate through the given string and build a new string that consists only of alphanumeric characters, converting them to lowercase.
2. Check for palindrome:
   • Use two-pointer technique to check if the cleaned string is a palindrome. One pointer will start from the beginning (left) and the other from the end (right).
   • Compare characters at left and right indices, and move the pointers towards the center.
   • If at any point characters at left and right indices do not match, return false.
   • If the loop completes without mismatches, return true.

Code:

#include <iostream>
#include <string>
#include <cctype>  // for isalnum and tolower

class Solution {
public:
    bool isPalindrome(std::string s) {
        std::string cleaned;
        
        // Build the cleaned version of the string
        for (char c : s) {
            if (std::isalnum(c)) {
                cleaned += std::tolower(c);
            }
        }
        
        // Use two-pointer technique to check palindrome
        int left = 0, right = cleaned.size() - 1;
        while (left < right) {
            if (cleaned[left] != cleaned[right]) {
                return false;
            }
            ++left;
            --right;
        }
        
        return true;
    }
};

// Example usage
int main() {
    Solution solution;
    std::string test1 = "A man, a plan, a canal: Panama";
    std::string test2 = "race a car";
    
    std::cout << std::boolalpha;
    std::cout << "Test 1: " << solution.isPalindrome(test1) << std::endl;
    std::cout << "Test 2: " << solution.isPalindrome(test2) << std::endl;
    
    return 0;
}

Time Complexity:

• Cleaning the string: O(n), where n is the length of the input string. We iterate through the string once to build the cleaned string.
• Checking for palindrome: O(m), where m is the length of the cleaned string (m ≤ n). We use two pointers to check the cleaned string.

Overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?