Palindrome Checker (In-Place)

Problem Description

Given a string containing alphanumeric and special characters, determine if it's a palindrome, ignoring special characters and case. The goal is to achieve this in-place, meaning without using extra space.

Approach

The approach involves using two pointers, one starting from the beginning of the string and the other from the end. We move these pointers towards each other, skipping non-alphanumeric characters and ignoring case, until they meet in the middle. If at any point the characters at the two pointers don't match, the string is not a palindrome.

Code

def is_palindrome_in_place(s):
 left = 0
 right = len(s) - 1

 while left < right:
 # Move left pointer to the next alphanumeric character
 while left < right and not s[left].isalnum():
 left += 1

 # Move right pointer to the previous alphanumeric character
 while left < right and not s[right].isalnum():
 right -= 1

 # Compare characters (case-insensitive)
 if s[left].lower() != s[right].lower():
 return False

 left += 1
 right -= 1

 return True

# Example usage
string1 = "12@#.Race@#car"
string2 = "A man, a plan, a canal: Panama"
string3 = "hello"

print(f"{string1}: {is_palindrome_in_place(string1)}")
print(f"{string2}: {is_palindrome_in_place(string2)}")
print(f"{string3}: {is_palindrome_in_place(string3)}")

Explanation

Initialization: Two pointers, left and right, are initialized to the start and end of the string, respectively.
Iteration: The while loop continues as long as left is less than right.
Skipping Non-Alphanumeric Characters: Inner while loops increment left and decrement right until they point to alphanumeric characters.
Case-Insensitive Comparison: The characters at s[left] and s[right] are converted to lowercase and compared. If they are not equal, the function returns False.
Pointer Movement: If the characters match, left is incremented and right is decremented to check the next pair of characters.
Palindrome Confirmation: If the loop completes without finding any mismatched characters, the function returns True.

Big(O) Run-time Analysis

The algorithm iterates through the string once, with the left and right pointers moving towards the middle. In the worst case, each pointer might have to traverse the entire string. Even though there are nested while loops, each character is visited a maximum of 4 times, so the time complexity is O(n), where n is the length of the string.

Big(O) Space Usage Analysis

The algorithm uses a constant amount of extra space for the left and right pointers. Therefore, the space complexity is O(1), indicating that it operates in-place.

Edge Cases

Empty String: An empty string is considered a palindrome.
String with Only Special Characters: The algorithm should correctly handle strings that contain only special characters.
Null or Undefined Input: Handle the cases where the input string is None or undefined to prevent errors.

def is_palindrome_in_place_safe(s):
 if s is None:
 return False  # Or raise an exception, depending on requirements

 left = 0
 right = len(s) - 1

 while left < right:
 # Move left pointer to the next alphanumeric character
 while left < right and not s[left].isalnum():
 left += 1

 # Move right pointer to the previous alphanumeric character
 while left < right and not s[right].isalnum():
 right -= 1

 # Compare characters (case-insensitive)
 if s[left].lower() != s[right].lower():
 return False

 left += 1
 right -= 1

 return True

# Example with None
string4 = None
print(f"{string4}: {is_palindrome_in_place_safe(string4)}")

Alternative Approaches

Using Regular Expressions: Regular expressions could be used to remove non-alphanumeric characters. However, this might involve creating a new string, which would not be in-place.
Pre-processing the String: Creating a new string containing only alphanumeric characters (in lowercase) and then checking if it's a palindrome. This is not in-place and has O(n) space complexity.

Check if a string is a palindrome in-place, ignoring special characters and case.