## 1. Clean and Reverse ### Intuition First create the exact string that matters: keep only alphanumeric characters and convert letters to lowercase. For example, `s = "Red rum"` becomes `"redrum"`. A string is a palindrome if it equals its reverse, so we can compare the cleaned string with its reversed version. This approach is straightforward, but it stores the entire cleaned string and its reverse even though we only need to compare matching characters. ### Algorithm 1. Build a cleaned string by keeping every alphanumeric character from `s` in lowercase. 2. Reverse the cleaned string. 3. Return whether the cleaned string equals its reverse. ### Code ```python def isPalindrome(s: str) -> bool: cleaned = "".join(char.lower() for char in s if char.isalnum()) # @viz:filter_alnum_lower reversed_cleaned = cleaned[::-1] # @viz:build_reversed return cleaned == reversed_cleaned # @viz:compare_clean_reversed ``` ```java class Solution { public boolean isPalindrome(String s) { StringBuilder cleaned = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (Character.isLetterOrDigit(c)) { cleaned.append(Character.toLowerCase(c)); } } String forward = cleaned.toString(); // @viz:filter_alnum_lower String backward = cleaned.reverse().toString(); // @viz:build_reversed return forward.equals(backward); // @viz:compare_clean_reversed } } ``` ```cpp #include using namespace std; bool isPalindrome(string s) { string cleaned; for (char c : s) { if (isalnum(c)) { cleaned += tolower(c); } } string forward = cleaned; // @viz:filter_alnum_lower string backward = cleaned; reverse(backward.begin(), backward.end()); // @viz:build_reversed return forward == backward; // @viz:compare_clean_reversed } ``` ```javascript /** * @param {string} s * @return {boolean} */ function isPalindrome(s) { const cleaned = s .toLowerCase() .split('') .filter(c => /^[a-z0-9]$/i.test(c)) .join(''); // @viz:filter_alnum_lower const reversed = cleaned.split('').reverse().join(''); // @viz:build_reversed return cleaned === reversed; // @viz:compare_clean_reversed } ``` ```go import ( "strings" ) func isPalindrome(s string) bool { var cleaned strings.Builder for _, r := range s { if (r >= 'a' && r <= 'z') || (r >= 'A' && r <= 'Z') || (r >= '0' && r <= '9') { cleaned.WriteRune(r | 32) // convert to lowercase by setting the 6th bit } } forward := cleaned.String() // @viz:filter_alnum_lower runes := []rune(forward) for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 { runes[i], runes[j] = runes[j], runes[i] } backward := string(runes) // @viz:build_reversed return forward == backward // @viz:compare_clean_reversed } ``` ### Complexity - **Time:** O(n), where `n` is the length of `s`. Cleaning and reversing each take linear time. - **Space:** O(n), where `n` is the length of `s`, for the cleaned string and its reverse. ## 2. Two Pointers on the Cleaned String ### Intuition After cleaning the input, compare characters from both ends moving toward the center. For example, if the cleaned string is `"raceacar"`, compare `r` with `r`, then `a` with `a`, and eventually `c` with `a`; that mismatch proves the string is not a palindrome. This avoids creating a reversed copy, but it still creates a separate cleaned string. We can avoid that extra storage by skipping irrelevant characters directly in the original input. ### Algorithm 1. Build a lowercase string containing only alphanumeric characters. 2. Set one pointer at the beginning and another at the end of the cleaned string. 3. While the pointers have not crossed: - If the characters differ, return `False`. - Move both pointers inward. 4. Return `True` if every pair matches. ### Code ```python def isPalindrome(s: str) -> bool: cleaned = "".join(char.lower() for char in s if char.isalnum()) # @viz:clean left, right = 0, len(cleaned) - 1 # @viz:init_pointers while left < right: # @viz:loop if cleaned[left] != cleaned[right]: # @viz:compare return False left += 1; right -= 1 # @viz:move_pointers return True # @viz:return_true ``` ```java class Solution { public boolean isPalindrome(String s) { StringBuilder cleaned = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) { cleaned.append(Character.toLowerCase(c)); } } // @viz:clean int left = 0, right = cleaned.length() - 1; // @viz:init_pointers while (left < right) { // @viz:loop if (cleaned.charAt(left) != cleaned.charAt(right)) { // @viz:compare return false; } left++; right--; // @viz:move_pointers } return true; // @viz:return_true } } ``` ```cpp #include using namespace std; bool isPalindrome(string s) { string cleaned; for (char c : s) { if (isalnum(c)) { cleaned += tolower(c); } } // @viz:clean int left = 0, right = cleaned.length() - 1; // @viz:init_pointers while (left < right) { // @viz:loop if (cleaned[left] != cleaned[right]) { // @viz:compare return false; } left++; right--; // @viz:move_pointers } return true; // @viz:return_true } ``` ```javascript /** * @param {string} s * @return {boolean} */ function isPalindrome(s) { let cleaned = ""; for (let i = 0; i < s.length; i++) { const ch = s[i]; if (/[a-zA-Z0-9]/.test(ch)) { cleaned += ch.toLowerCase(); } } // @viz:clean let left = 0, right = cleaned.length - 1; // @viz:init_pointers while (left < right) { // @viz:loop if (cleaned[left] !== cleaned[right]) { // @viz:compare return false; } left++; right--; // @viz:move_pointers } return true; // @viz:return_true } ``` ```go func isPalindrome(s string) bool { cleaned := "" for _, ch := range s { if (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9') { if ch >= 'A' && ch <= 'Z' { ch = ch + 32 // to lowercase } cleaned += string(ch) } } // @viz:clean left, right := 0, len(cleaned)-1 // @viz:init_pointers for left < right { // @viz:loop if cleaned[left] != cleaned[right] { // @viz:compare return false } left++; right-- // @viz:move_pointers } return true // @viz:return_true } ``` ### Complexity - **Time:** O(n), where `n` is the length of `s`. Each character is processed a constant number of times. - **Space:** O(n), where `n` is the length of `s`, for the cleaned string. ## 3. Two Pointers with In-Place Scanning ### Intuition The cleaning step does not need to happen ahead of time. Use one pointer at each end of the original string and skip non-alphanumeric characters as they are encountered. For example, in `"A man, a plan"`, the left pointer skips punctuation and spaces while the right pointer does the same from the other side. Once both pointers point to meaningful characters, compare them case-insensitively. This keeps the same O(n) running time while using O(1) additional space. ### Algorithm 1. Set `left` to the first index and `right` to the last index of `s`. 2. While `left` is less than `right`: 1. Move `left` forward while it points to a non-alphanumeric character. 2. Move `right` backward while it points to a non-alphanumeric character. 3. Compare `s[left]` and `s[right]` after converting both to lowercase. 4. If they differ, return `False`. 5. Move both pointers inward. 3. Return `True` after all comparable pairs match. ### Code ```python def isPalindrome(s: str) -> bool: left, right = 0, len(s) - 1 # @viz:init_pointers while left < right: # @viz:outer_loop while left < right and not s[left].isalnum(): # @viz:skip_left left += 1 while left < right and not s[right].isalnum(): # @viz:skip_right right -= 1 if s[left].lower() != s[right].lower(): # @viz:compare return False left += 1 # @viz:move_pointers right -= 1 return True # @viz:return_true ``` ```java class Solution { public boolean isPalindrome(String s) { int left = 0, right = s.length() - 1; // @viz:init_pointers while (left < right) { // @viz:outer_loop while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { // @viz:skip_left left++; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { // @viz:skip_right right--; } if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { // @viz:compare return false; } left++; // @viz:move_pointers right--; } return true; // @viz:return_true } } ``` ```cpp #include using namespace std; bool isPalindrome(string s) { int left = 0, right = s.length() - 1; // @viz:init_pointers while (left < right) { // @viz:outer_loop while (left < right && !isalnum(s[left])) { // @viz:skip_left left++; } while (left < right && !isalnum(s[right])) { // @viz:skip_right right--; } if (tolower(s[left]) != tolower(s[right])) { // @viz:compare return false; } left++; // @viz:move_pointers right--; } return true; // @viz:return_true } ``` ```javascript /** * @param {string} s * @return {boolean} */ function isPalindrome(s) { let left = 0, right = s.length - 1; // @viz:init_pointers while (left < right) { // @viz:outer_loop while (left < right && !/[a-z0-9]/i.test(s[left])) { // @viz:skip_left left++; } while (left < right && !/[a-z0-9]/i.test(s[right])) { // @viz:skip_right right--; } if (s[left].toLowerCase() !== s[right].toLowerCase()) { // @viz:compare return false; } left++; // @viz:move_pointers right--; } return true; // @viz:return_true } ``` ```go func isAlnum(c byte) bool { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') } func toLower(c byte) byte { if c >= 'A' && c <= 'Z' { return c + 32 } return c } func isPalindrome(s string) bool { left, right := 0, len(s)-1 // @viz:init_pointers for left < right { // @viz:outer_loop for left < right && !isAlnum(s[left]) { // @viz:skip_left left++ } for left < right && !isAlnum(s[right]) { // @viz:skip_right right-- } if toLower(s[left]) != toLower(s[right]) { // @viz:compare return false } left++ // @viz:move_pointers right-- } return true // @viz:return_true } ``` ### Complexity - **Time:** O(n), where `n` is the length of `s`. Each pointer moves only forward or backward through the string. - **Space:** O(1), excluding the input string, because only the two pointers and constant temporary values are used. ## Common Pitfalls - **Comparing punctuation or spaces:** Non-alphanumeric characters must be skipped before comparison. For example, the space in `"a b"` is not part of the cleaned string. - **Forgetting case-insensitive comparison:** `A` and `a` represent the same cleaned character. Use `.lower()` or an equivalent case normalization. - **Incorrect pointer bounds:** Keep `left < right` while skipping characters so the pointers do not pass each other or compare an invalid pair. An input containing only spaces should return `True` because its cleaned string is empty.

Palindrome Detection

Example

Palindrome Detection

Example