Palindrome Check 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

Note:

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 linear time and uses constant space.

Approach

To solve this problem, we can use a two-pointer technique:

Initialize one pointer at the beginning of the string and another at the end.
Compare the characters at these pointers.
If they are equal, move the pointers towards each other and continue the comparison.
If they are not equal, the string is not a palindrome.
If the pointers cross each other without finding any unequal characters, the string is a palindrome.

This approach ensures that we only traverse the string once, achieving O(n) time complexity, and we use only a few extra variables, maintaining O(1) space complexity.

Algorithm

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

Initialize two pointers, i at the start (0) and j at the end (n-1) of the string.
While i < j:
- Check if s[i] != s[j]. If true, return false.
- Increment i and decrement j.
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) {
        // Check if characters at i and j are not equal
        if (s[i] != s[j]) {
            return false; // Not a palindrome
        }
        // Move pointers towards the center
        i++;
        j--;
    }
    return true; // String is a palindrome
}

int main() {
    std::string str1 = "madam racecar madam";
    std::string str2 = "abcbx";

    std::cout << "Is \"" << str1 << "\" a palindrome? " << (isPalindrome(str1) ? "true" : "false") << std::endl;
    std::cout << "Is \"" << str2 << "\" a palindrome? " << (isPalindrome(str2) ? "true" : "false") << 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 few extra variables.

Edge Cases

Consider the following edge cases:

An empty string: Should return true as an empty string is trivially a palindrome.
A single character string: Should return true as a single character reads the same backward.
Strings with special characters and spaces: Depending on the problem requirements, you may need to handle these cases separately.

Testing

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

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

Use a variety of test cases to ensure the solution handles all scenarios correctly.

Thinking and Problem-Solving Tips

When approaching such problems:

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

Conclusion

Understanding and solving palindrome problems is crucial for developing strong problem-solving skills. Practice regularly and explore different algorithms to enhance your understanding.

Additional Resources

For further reading and practice: