1. Understanding the Problem

You are given a string s. Your task is to determine if it is a palindrome. A string is a palindrome if it reads the same forward and backward.

The Core Constraints (The Catch):

You cannot just read the raw string as-is. You must first clean it up based on two rules:

• Convert all uppercase letters to lowercase letters.
• Remove all non-alphanumeric characters (spaces, punctuation, symbols).

A Quick Example

Imagine the string: "A man, a plan, a canal: Panama".

After converting to lowercase and stripping punctuation and spaces, it becomes: "amanaplanacanalpanama".

If you read that forward and backward, it is identical. Therefore, the answer is True.

2. The Naive Approach (Creating a New String)

The most intuitive approach is to follow the instructions literally step-by-step.

You would loop through the original string, check if each character is a letter or number, and if it is, add its lowercase version to a brand-new string. Finally, you would reverse this new string and check if it matches the un-reversed version.

Trade-off Analysis

While this gets the job done and is easy to read, it wastes memory:

• Time Complexity: O(N) — You iterate through the string to clean it, and again to reverse and compare.
• Space Complexity: O(N) — You are creating a brand-new string in memory. In an enterprise system processing massive text payloads, creating duplicate data structures is highly inefficient.

3. The Optimal Approach: Two Pointers (In-Place)

To write production-grade code, we want to solve this with O(1) space complexity. We can do this by never creating a new string. Instead, we use two "pointers" (variables storing index positions) to inspect the original string from both ends simultaneously.

We place one pointer at the very beginning of the string and one at the very end. They step toward the middle, completely ignoring spaces and punctuation. When they land on valid letters or numbers, we compare them. If they ever mismatch, it's not a palindrome. If they successfully cross paths in the middle, we have a valid palindrome.

4. The Logic Step-by-Step

1. Initialize a left pointer at index 0.
2. Initialize a right pointer at the last index of the string (length - 1).
3. While left is less than right:
   • If the character at left is NOT alphanumeric, move left forward by 1 step.
   • If the character at right is NOT alphanumeric, move right backward by 1 step.
   • If BOTH are alphanumeric, compare their lowercase values.
     • If they do not match, return False immediately.
     • If they do match, move left forward by 1 and right backward by 1.
4. If the loop finishes without returning False, the string is a palindrome. Return True.

5. Complexity Analysis

• Time Complexity: O(N) — In the worst-case scenario, we traverse the entire string exactly once.
• Space Complexity: O(1) — We only use two integer variables (the pointers), meaning this requires practically zero extra memory regardless of the string's size.

6. Code Implementations

Expand the sections below to see the optimal O(1) space implementations across different languages.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        
        while left < right:
            # Move left pointer if not alphanumeric
            if not s[left].isalnum():
                left += 1
            # Move right pointer if not alphanumeric
            elif not s[right].isalnum():
                right -= 1
            # Both are alphanumeric, compare them
            else:
                if s[left].lower() != s[right].lower():
                    return False
                left += 1
                right -= 1
                
        return True

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            char charLeft = s.charAt(left);
            char charRight = s.charAt(right);
            
            // Move left pointer if not alphanumeric
            if (!Character.isLetterOrDigit(charLeft)) {
                left++;
            } 
            // Move right pointer if not alphanumeric
            else if (!Character.isLetterOrDigit(charRight)) {
                right--;
            } 
            // Both are alphanumeric, compare them
            else {
                if (Character.toLowerCase(charLeft) != Character.toLowerCase(charRight)) {
                    return false;
                }
                left++;
                right--;
            }
        }
        
        return true;
    }
}

#include <string>
#include <cctype>

class Solution {
public:
    bool isPalindrome(std::string s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            // Move left pointer if not alphanumeric
            if (!isalnum(s[left])) {
                left++;
            }
            // Move right pointer if not alphanumeric
            else if (!isalnum(s[right])) {
                right--;
            }
            // Both are alphanumeric, compare them
            else {
                if (tolower(s[left]) != tolower(s[right])) {
                    return false;
                }
                left++;
                right--;
            }
        }
        
        return true;
    }
};

7. Conclusion: You Are Ready

Congratulations, you just added the Two-Pointer pattern to your algorithmic toolkit. By recognizing that you can inspect data from both ends simultaneously, you transformed an inefficient, memory-heavy approach into a clean, O(1) space solution. This pattern is foundational for countless advanced array and string problems you will see in technical interviews. Keep practicing, sketch the pointers out on a whiteboard, and you will quickly master this technique!