Start learning free

LESSON 244 OF 410 · TWO POINTERS

Palindrome Check 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 6
    Ctrl + Enter to check

    PYTHON · TWO POINTERS

    Palindrome Check in Python, explained

    Problem Definition

    The problem requires us to determine if a given string is a palindrome. A palindrome is a sequence of characters that reads the same backward as forward.

    Input: A string s.

    Output: A boolean value true if the string is a palindrome, otherwise false.

    Constraints:

    • The algorithm should run in O(n) time.
    • The algorithm should use O(1) extra space.

    Example:

    Input:  "madam racecar madam"
Output: true
    Input:  "abcbx"
Output: false

    Understanding the Problem

    The core challenge is to check if the string reads the same backward as forward. This problem is significant in various applications such as text processing, data validation, and more. A common pitfall is to use extra space or not achieve the required time complexity.

    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, 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 constant amount of extra space, achieving 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.
      • Move i one step to the right.
      • Move j one step to the left.
    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 pointers do not match, 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, the string is a palindrome
    return True

# Example usage
print(is_palindrome("madam racecar madam"))  # Output: True
print(is_palindrome("abcbx"))  # Output: False

    Complexity Analysis

    Time Complexity: O(n), where n is the length of the string. We traverse the string once.

    Space Complexity: O(1), as we use a constant amount of extra space for the pointers.

    Edge Cases

    Consider the following edge cases:

    • Empty string: Should return true.
    • Single character string: Should return true.
    • Strings with special characters and spaces: Ensure the algorithm handles them correctly.
    # Edge case examples
print(is_palindrome(""))  # Output: True
print(is_palindrome("a"))  # Output: True
print(is_palindrome("A man, a plan, a canal, Panama"))  # Output: False (case-sensitive and includes spaces)

    Testing

    To test the solution comprehensively, consider a variety of test cases:

    • Simple palindromes and non-palindromes.
    • Edge cases like empty strings and single characters.
    • Strings with mixed characters.

    Using a testing framework like unittest in Python can help automate and organize these tests.

    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 problem-solving skills.

    Conclusion

    Understanding and solving palindrome problems is crucial for text processing and data validation. The two-pointer technique is an efficient way to achieve the desired time and space complexity. Practice and exploration of similar problems can further enhance problem-solving skills.

    Additional Resources

    For further reading and practice:

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