Start learning free

LESSON 243 OF 409 · TWO POINTERS

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

Practice O(n) Read the full explanation

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 (the two-pointer approach below achieves this).


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • the character at index 0 equals the character at index n - 1
  • the character at index 1 equals the character at index n - 2
  • the character at index 2 equals the character at index n - 3
  • ...
How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers through the algorithm?

For as long as i < j:
  • 1. We should check if the characters at indices i and j are different, and if so, we conclude the string is not a palindrome and return false.
  • 2. Move i one step to the right.
  • 3. Move j one step to the left.
  • 4. Go to step 1.
If i became greater than or equal to j and we haven't returned false, then we can conclude the string is a palindrome and return true.

STEP 1 OF 6
    Ctrl + Enter to check

    C++ · TWO POINTERS

    Palindrome Check in C++, explained

    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:

    1. Initialize two pointers, i at the start (0) and j at the end (n-1) of the string.
    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) {
        // 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:

    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free