Palindrome Check II in C++ with O(n) Time Complexity

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward

Example 1:

Input:  "madam racecar madam"

Output: true

Example 2:

Input:  "abcbx"

Output: false

Your algorithm should run in O(n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to determine if a given string reads the same backward as forward. This is significant in various applications such as text processing, data validation, and more. A common pitfall is to overlook the need for an efficient solution that runs in O(n) time and uses O(1) extra space.

Approach

To solve this problem, we can use a two-pointer technique. One pointer starts at the beginning of the string, and the other starts at the end. We compare the characters at these pointers and move them towards the center. If all corresponding characters are equal, the string is a palindrome.

Naive Solution

A naive solution would involve reversing the string and comparing it to the original. However, this approach uses O(n) extra space and is not optimal.

Optimized Solution

The optimized solution uses two pointers:

• Initialize one pointer at the start (i = 0) and the other at the end (j = n - 1).
• While i < j, compare the characters at these pointers.
• If the characters are not equal, return false.
• Move the pointers towards the center (i++, j--).
• If all characters match, return true.

Algorithm

Here is a step-by-step breakdown of the algorithm:

1. Initialize two pointers, i and j.
2. While i < j:
   • Check if s[i] != s[j]. If true, return false.
   • Increment i and decrement j.
3. If the loop completes without returning false, return true.

Code Implementation

#include <iostream>
#include <string>

bool isPalindrome(const std::string& s) {
    int i = 0;
    int j = s.length() - 1;
    
    while (i < j) {
        // Compare characters at i and j
        if (s[i] != s[j]) {
            return false; // Not a palindrome
        }
        i++;
        j--;
    }
    return true; // Is a palindrome
}

int main() {
    std::string str1 = "madam racecar madam";
    std::string str2 = "abcbx";
    
    std::cout << std::boolalpha; // Print bools as true/false
    std::cout << "Is \"" << str1 << "\" a palindrome? " << isPalindrome(str1) << std::endl;
    std::cout << "Is \"" << str2 << "\" a palindrome? " << isPalindrome(str2) << std::endl;
    
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n) because we traverse the string once. The space complexity is O(1) as we only use a constant amount of extra space for the pointers.

Edge Cases

Consider the following edge cases:

• Empty string: Should return true.
• Single character: Should return true.
• Strings with special characters and spaces: Ensure they are handled correctly.

Testing

To test the solution comprehensively, consider the following test cases:

• Simple palindromes: "madam", "racecar"
• Non-palindromes: "hello", "world"
• Edge cases: "", "a", "ab"

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller parts.
• Think about different approaches and their trade-offs.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to determine if a string is a palindrome using an efficient O(n) time and O(1) space algorithm. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Valid Palindrome
• GeeksforGeeks: Check if a string is a palindrome
• HackerRank: Palindrome Index