5 Best Ways to Check if Characters in a String Form a Palindrome in O(1) Extra Space in Python

Rate this post

πŸ’‘ Problem Formulation: A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization). This article demonstrates how to check whether the characters in a string form a palindrome using Python with O(1) extra space. For example, given the input “racecar”, the desired output would be True because “racecar” is a palindrome.

Method 1: Two Pointers

This method involves using two pointers that move towards the center from the start and end of the string respectively, comparing characters at each step. It requires O(1) extra space since no additional data structures are used and a simple loop traverses the string only once.

Here’s an example:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left].lower() != s[right].lower():
            return False
        left, right = left + 1, right - 1
    return True

print(is_palindrome("Racecar"))

Output: True

In this code snippet, two pointers are initialized at the start and end of the string. The loop continues until they meet in the middle, comparing each pair of characters after converting them to lowercase. If any pair doesn’t match, it returns False; otherwise, after fully traversing, it returns True.

Method 2: Recursion

The recursive approach checks palindromes by comparing the first and last characters of the string, then recursively calling the function with the middle substring. The base cases handle empty or single-character strings, which are trivially palindromes.

Here’s an example:

def is_palindrome(s, start, end):
    if start >= end:
        return True
    return (s[start].lower() == s[end].lower()) and is_palindrome(s, start + 1, end - 1)

print(is_palindrome("Racecar", 0, len("Racecar") - 1))

Output: True

This snippet uses recursion by shrinking the problem size in each call, checking the first and last characters, and invoking itself with the next inner section of the string. It’s an elegant solution but may risk a stack overflow error on very long strings.

Method 3: Reverse and Compare

By reversing the string and comparing it to the original, we can check for a palindrome. Although string reversal sounds like an O(n) extra space task, Python’s slicing can be described as an O(1) extra space operation due to its implementation in CPython where it reuses the bytes of the original string.

Here’s an example:

def is_palindrome(s):
    return s.lower() == s[::-1].lower()

print(is_palindrome("Racecar"))

Output: True

The code compares the original lowercased string with its reverse. Python’s slicing with [::-1] elegantly achieves the string reversal. It’s a concise method, but some might argue it doesn’t strictly adhere to O(1) space due to the creation of a reversed copy. However, Python optimizes this operation internally.

Method 4: In-Place String Modification

Python strings are immutable, so it is not possible to modify them in place. However, it is theoretically possible to convert the string into a list of characters and perform in-place reversal comparison.

Here’s an example:

# Not recommended due to conversion, listed only for conceptual purposes
def is_palindrome(s):
    s_list = list(s.lower())
    left, right = 0, len(s_list) - 1
    while left < right:
        if s_list[left] != s_list[right]:
            return False
        left, right = left + 1, right - 1
    return True

print(is_palindrome("Racecar"))

Output: True

This method is not recommended since converting the string to a list increases space complexity to O(n), but conceptually, this is how in-place modification would work if Python strings were mutable.

Bonus One-Liner Method 5: Pythonic Approach

For those who prefer succinct code, Python provides the ability to express complex functionality in a single line. Here’s a Python one-liner that uses all lowercase conversion and slicing for comparison.

Here’s an example:

is_palindrome = lambda s: s.lower() == s[::-1].lower()

print(is_palindrome("Racecar"))

Output: True

This one-liner leverages a lambda function and Python’s slicing to achieve the same goal. It’s a compact, Pythonic expression but follows the same debate as method 3 regarding the O(1) space constraint.

Summary/Discussion

  • Method 1: Two Pointers. Simple and intuitive. True O(1) extra space. Cannot handle complex cases like ignoring punctuation without additional logic.
  • Method 2: Recursion. Elegant and straightforward. Risk of stack overflow for long strings. Questions over true O(1) space due to stack frame usage.
  • Method 3: Reverse and Compare. Pythonic and concise. Arguably not O(1) extra space due to reversed string copy, but optimized in CPython.
  • Method 4: In-Place String Modification. Not applicable to Python strings due to immutability. Theoretical interest only, with practical O(n) space usage for string-to-list conversion.
  • Method 5: Pythonic One-Liner. Highly succinct. Same space complexity considerations as method 3. Preferable for code golf or when brevity is valued.