Is Palindrome Valid
Given a string s, determine if it is a palindrome after converting
all uppercase letters to lowercase and removing all non-alphanumeric
characters (spaces, punctuation, etc.). An empty string (after
filtering) is considered a valid palindrome.
Solve it using O(1) extra space — do not build a cleaned copy of the string and compare it to its reverse; scan the original string in place with two pointers instead.
Example 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After filtering and lowercasing: "amanaplanacanalpanama",
which reads the same forwards and backwards.
Example 2
Input: s = "race a car"
Output: false
Explanation: Filtered: "raceacar", which is not a palindrome.
Constraints
1 <= s.length <= 2 * 10^5sconsists of printable ASCII characters.
Use two pointers, left starting at the beginning of the string and
right at the end. At each step, advance left forward past any
character that isn't alphanumeric, and move right backward past any
character that isn't alphanumeric. Once both point at alphanumeric
characters, compare them case-insensitively; if they differ, the
string is not a palindrome. If they match, move both pointers inward
and repeat until they meet or cross.
This avoids allocating a separate cleaned string (which a naive "filter then reverse and compare" approach would need), so it runs in O(1) extra space instead of O(n).
def is_palindrome_valid(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Complexity: O(n) time, since each character is visited by at most one of the two pointers. O(1) extra space, since no copy of the string is created.
Share this question