Start learning free

LESSON 196 OF 410 · STRINGS

Palindrome Check II in Python 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 2
    Ctrl + Enter to check

    PYTHON · STRINGS

    Palindrome Check in Python, 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.

    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 two-pointer technique is optimal because it runs in O(n) time and uses O(1) extra space. Here’s how to implement it:

    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

    def is_palindrome(s: str) -> bool:
    # Initialize two pointers
    i, j = 0, len(s) - 1
    
    # Loop until the pointers cross
    while i < j:
        # If characters at i and j are not equal, it's not a palindrome
        if s[i] != s[j]:
            return False
        # Move the pointers towards each other
        i += 1
        j -= 1
    
    # If we complete the loop without finding a mismatch, it's a palindrome
    return True

# Test cases
print(is_palindrome("madam racecar madam"))  # Output: True
print(is_palindrome("abcbx"))  # Output: False

    Complexity Analysis

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

    Edge Cases

    Consider the following edge cases:

    • Empty string: Should return True as an empty string is trivially a palindrome.
    • Single character string: Should return True as a single character is a palindrome.
    • Strings with special characters and spaces: Ensure the algorithm handles these 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

    Understanding and solving palindrome problems is crucial for various applications. The two-pointer technique provides an efficient solution with O(n) time complexity and O(1) space complexity. Practice and explore further to master such problems.

    Additional Resources

    For further reading and practice, consider the following resources:

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