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

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

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

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: