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

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:

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.
- Move i one step to the right.
- Move j one step to the left.
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: