#13 · Two Pointers

Valid Palindrome

After lowercasing and removing every non-alphanumeric character, a phrase is a palindrome if it reads the same forwards and backwards. Given a string, return true if it is a palindrome.

EasyLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Two pointers moving inward

A palindrome is symmetric, so the i-th character from the left must equal the i-th from the right. Two indices, one at each end, walk toward each other and compare mirrored characters.

Memory layout

Two integers over the original contiguous character buffer: no allocation, sequential access from both ends, which is cache friendly.

Operation	Cost
compare one mirrored pair	O(1)
whole check	O(n)
extra space	O(1)

Cleaned copy of the string

Filtering and lowercasing produces a new string where plain index comparison works. It simplifies the loop at the price of an extra O(n) string.

Memory layout

A new contiguous buffer (strings are immutable in most languages, so each filter/reverse step allocates another one).

Operation	Cost
build cleaned copy	O(n) time, O(n) space
reverse copy	O(n) time, O(n) space

Why it fits

Palindrome is defined by symmetry, and two inward-moving pointers test exactly that symmetry with no more than n/2 comparisons.
Skipping irrelevant characters with the pointers themselves removes the need for a cleaned copy, which brings extra space down from O(n) to O(1).
The loop can stop at the first mismatch, so non-palindromes are often rejected much earlier than n/2 steps.

Why alternatives degrade

Reverse the string and compare:: Correct, but allocates one or more O(n) strings and always does the full n comparisons; it also cannot exit early.
Recursion on substrings:: Creates O(n) stack frames and (in many languages) O(n²) copied substrings.
Regex to detect palindromes:: Palindromes are not a regular language; regex cannot express "mirror of what came before".

Four approaches, from naive to production

1 · beginner

Clean, reverse, compare

time O(n)space O(n)

Strip non-alphanumeric characters and lowercase, build the reversed string, and check that the two are equal.

bool isPalindrome(string s) {
    string cleaned;
    for (char c : s) if (isalnum((unsigned char)c)) cleaned += tolower((unsigned char)c);
    string reversed(cleaned.rbegin(), cleaned.rend());
    return cleaned == reversed;
}

public boolean isPalindrome(String s) {
    String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", "");
    String reversed = new StringBuilder(cleaned).reverse().toString();
    return cleaned.equals(reversed);
}

def is_palindrome(s: str) -> bool:
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    reversed_s = cleaned[::-1]
    return cleaned == reversed_s

function isPalindrome(s: string): boolean {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  const reversed = cleaned.split('').reverse().join('');
  return cleaned === reversed;
}

Flaws & bottlenecks

Allocates at least two new strings (cleaned and reversed), plus intermediate arrays from split / reverse.
Always does the whole O(n) comparison; a mismatch at the first character is not detected early.
The regex and the split/reverse/join chain hide several full passes over the data.

Interviewer cross-questions

Can you avoid building the reversed string?

Say: Yes. Compare each character with its mirror position using two indices, so you never materialize the reverse. That halves the work (n/2 comparisons) and removes one O(n) allocation.

What is the real time complexity?

Say: O(n): the filter pass, the reverse pass, and the comparison are each linear. The constant is larger than it looks, because each step allocates.

What counts as the "same" character?

Say: The problem says ignore case and non-alphanumerics, so "A" matches "a" and punctuation is invisible. Clarify this with the interviewer, since unicode letters or accents would need normalization.

2 · intermediate

Clean once, then two pointers

time O(n)space O(n)

Build the cleaned string, then compare s[left] with s[right] while the pointers close in. No reversed copy is needed.

bool isPalindrome(string s) {
    string cleaned;
    for (char c : s) if (isalnum((unsigned char)c)) cleaned += tolower((unsigned char)c);
    int left = 0;
    int right = (int)cleaned.size() - 1;
    while (left < right) {
        if (cleaned[left] != cleaned[right]) return false;
        left++;
        right--;
    }
    return true;
}

public boolean isPalindrome(String s) {
    String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", "");
    int left = 0;
    int right = cleaned.length() - 1;
    while (left < right) {
        if (cleaned.charAt(left) != cleaned.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

def is_palindrome(s: str) -> bool:
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    left = 0
    right = len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]: return False
        left += 1
        right -= 1
    return True

function isPalindrome(s: string): boolean {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let left = 0;
  let right = cleaned.length - 1;
  while (left < right) {
    if (cleaned[left] !== cleaned[right]) return false;
    left++;
    right--;
  }
  return true;
}

Flaws & bottlenecks

Still allocates the cleaned string: O(n) extra memory for input that was already usable in place.
The cleaning pass touches every character even when the first pair already mismatches.
The regex is compiled and run over the whole input before any comparison.

Interviewer cross-questions

Why is the two-pointer loop enough?

Say: A string is a palindrome iff s[i] equals s[n−1−i] for every i < n/2. Two pointers walk through exactly those pairs, so n/2 comparisons suffice, and the first mismatch ends the search.

Can you drop the cleaned copy?

Say: Yes: let the pointers skip non-alphanumeric characters in place, comparing case-insensitively. That gives O(1) extra space, which is the advanced approach.

What are the edge cases?

Say: The empty string and strings with only punctuation (both palindromes by this definition), a single character, and mixed case such as "Aa".

3 · advanced

Two pointers that skip in place

time O(n)space O(1)

Work on the original string: advance left past non-alphanumeric characters, retreat right past them, then compare the two letters ignoring case.

bool isPalindrome(string s) {
    int left = 0;
    int right = (int)s.size() - 1;
    auto isAlnum = [](char c) { return isalnum((unsigned char)c) != 0; };
    while (left < right) {
        while (left < right && !isAlnum(s[left])) left++;
        while (left < right && !isAlnum(s[right])) right--;
        if (tolower((unsigned char)s[left]) != tolower((unsigned char)s[right])) return false;
        left++;
        right--;
    }
    return true;
}

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    java.util.function.IntPredicate isAlnum = Character::isLetterOrDigit;
    while (left < right) {
        while (left < right && !isAlnum.test(s.charAt(left))) left++;
        while (left < right && !isAlnum.test(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
        left++;
        right--;
    }
    return true;
}

def is_palindrome(s: str) -> bool:
    left = 0
    right = 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

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
  const isAlnum = (c: string) => /[a-z0-9]/i.test(c);
  while (left < right) {
    while (left < right && !isAlnum(s[left])) left++;
    while (left < right && !isAlnum(s[right])) right--;
    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
    left++;
    right--;
  }
  return true;
}

Flaws & bottlenecks

Each iteration calls a regex test per character and lowercases two characters: more per-character overhead than needed.
The nested skip loops each re-check left < right, which is easy to get wrong (omitting it can run past the other pointer).
A character-class regex like [a-z0-9] only understands ASCII; accented letters are treated as punctuation.

Interviewer cross-questions

Why do the inner skip loops also test left < right?

Say: If the rest of the string is all punctuation, an unguarded skip loop would run left past right (or off the end of the string). The guard keeps both pointers inside the unvisited region.

Is it still O(n) with nested while loops?

Say: Yes: left only moves right and right only moves left, and together they visit each character at most once, so total pointer movement is at most n regardless of the nesting.

How would you support Unicode?

Say: Normalize first (NFC or NFKD, stripping combining marks) and use a Unicode-aware letter test (the \p{L} and \p{N} property classes, or a library). Iterate by code point, not code unit, so surrogate pairs are not split.

4 · expert

Character codes, no regex, no allocation

time O(n)space O(1)

The same in-place two-pointer loop, but it reads integer character codes, tests alphanumerics with range comparisons, and folds case with a single OR against 32.

static inline bool isAlnumCode(int c) { return (c >= 48 && c <= 57) || ((c | 32) >= 97 && (c | 32) <= 122); }

bool isPalindrome(const string& s) {
    int left = 0;
    int right = (int)s.size() - 1;
    while (left < right) {
        int a = (unsigned char)s[left];
        int b = (unsigned char)s[right];
        if (!isAlnumCode(a)) { left++; continue; }
        if (!isAlnumCode(b)) { right--; continue; }
        if ((a | 32) != (b | 32)) return false;
        left++;
        right--;
    }
    return true;
}

private static boolean isAlnumCode(int c) { return (c >= 48 && c <= 57) || ((c | 32) >= 97 && (c | 32) <= 122); }

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        int a = s.charAt(left);
        int b = s.charAt(right);
        if (!isAlnumCode(a)) { left++; continue; }
        if (!isAlnumCode(b)) { right--; continue; }
        if ((a | 32) != (b | 32)) return false;
        left++;
        right--;
    }
    return true;
}

def _is_alnum_code(c: int) -> bool: return 48 <= c <= 57 or 97 <= (c | 32) <= 122

def is_palindrome(s: str) -> bool:
    left = 0
    right = len(s) - 1
    while left < right:
        a = ord(s[left])
        b = ord(s[right])
        if not _is_alnum_code(a):
            left += 1
            continue
        if not _is_alnum_code(b):
            right -= 1
            continue
        if (a | 32) != (b | 32): return False
        left += 1
        right -= 1
    return True

const isAlnumCode = (c: number) => (c >= 48 && c <= 57) || ((c | 32) >= 97 && (c | 32) <= 122);

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    const a = s.charCodeAt(left);
    const b = s.charCodeAt(right);
    if (!isAlnumCode(a)) { left++; continue; }
    if (!isAlnumCode(b)) { right--; continue; }
    if ((a | 32) !== (b | 32)) return false;
    left++;
    right--;
  }
  return true;
}

Flaws & bottlenecks

ASCII only: any non-ASCII character is treated as punctuation and skipped, which is wrong for accented or non-Latin text.
The (c | 32) fold relies on ASCII layout and is easy to misapply: it is only valid after confirming the code is a letter or digit.
Less readable than a regex or toLowerCase(); it needs a comment and unit tests to be maintainable.

Interviewer cross-questions

Why does OR-ing with 32 fold case?

Say: In ASCII, upper-case letters 65–90 differ from lower-case 97–122 by exactly bit 5 (value 32). Setting that bit maps A–Z onto a–z. It is only safe once we know the code is a letter or digit; applied to other characters it can corrupt them (for example 64 "@" becomes 96).

Why is this faster than the regex version?

Say: It avoids calling into the regex engine and creating one-character strings per iteration. charCodeAt returns an integer and the tests are a few integer comparisons, so the JIT can keep everything in registers.

What would you test?

Say: Empty string, only punctuation, single character, mixed case ("Aa"), digits versus letters ("0P" must be false), leading/trailing punctuation, a long palindrome, and a non-palindrome that differs only in the middle.

Synchronized code walkthrough

Showing: Clean, reverse, compare — shares the player above; click any step to jump.

bool isPalindrome(string s) {
    string cleaned;
    for (char c : s) if (isalnum((unsigned char)c)) cleaned += tolower((unsigned char)c);
    string reversed(cleaned.rbegin(), cleaned.rend());
    return cleaned == reversed;
}

public boolean isPalindrome(String s) {
    String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", "");
    String reversed = new StringBuilder(cleaned).reverse().toString();
    return cleaned.equals(reversed);
}

def is_palindrome(s: str) -> bool:
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    reversed_s = cleaned[::-1]
    return cleaned == reversed_s

function isPalindrome(s: string): boolean {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  const reversed = cleaned.split('').reverse().join('');
  return cleaned === reversed;
}

bool isPalindrome(string s) {
    string cleaned;
    for (char c : s) if (isalnum((unsigned char)c)) cleaned += tolower((unsigned char)c);
    int left = 0;
    int right = (int)cleaned.size() - 1;
    while (left < right) {
        if (cleaned[left] != cleaned[right]) return false;
        left++;
        right--;
    }
    return true;
}

public boolean isPalindrome(String s) {
    String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", "");
    int left = 0;
    int right = cleaned.length() - 1;
    while (left < right) {
        if (cleaned.charAt(left) != cleaned.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

def is_palindrome(s: str) -> bool:
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    left = 0
    right = len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]: return False
        left += 1
        right -= 1
    return True

function isPalindrome(s: string): boolean {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let left = 0;
  let right = cleaned.length - 1;
  while (left < right) {
    if (cleaned[left] !== cleaned[right]) return false;
    left++;
    right--;
  }
  return true;
}

bool isPalindrome(string s) {
    int left = 0;
    int right = (int)s.size() - 1;
    auto isAlnum = [](char c) { return isalnum((unsigned char)c) != 0; };
    while (left < right) {
        while (left < right && !isAlnum(s[left])) left++;
        while (left < right && !isAlnum(s[right])) right--;
        if (tolower((unsigned char)s[left]) != tolower((unsigned char)s[right])) return false;
        left++;
        right--;
    }
    return true;
}

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    java.util.function.IntPredicate isAlnum = Character::isLetterOrDigit;
    while (left < right) {
        while (left < right && !isAlnum.test(s.charAt(left))) left++;
        while (left < right && !isAlnum.test(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
        left++;
        right--;
    }
    return true;
}

def is_palindrome(s: str) -> bool:
    left = 0
    right = 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

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
  const isAlnum = (c: string) => /[a-z0-9]/i.test(c);
  while (left < right) {
    while (left < right && !isAlnum(s[left])) left++;
    while (left < right && !isAlnum(s[right])) right--;
    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
    left++;
    right--;
  }
  return true;
}

static inline bool isAlnumCode(int c) { return (c >= 48 && c <= 57) || ((c | 32) >= 97 && (c | 32) <= 122); }

bool isPalindrome(const string& s) {
    int left = 0;
    int right = (int)s.size() - 1;
    while (left < right) {
        int a = (unsigned char)s[left];
        int b = (unsigned char)s[right];
        if (!isAlnumCode(a)) { left++; continue; }
        if (!isAlnumCode(b)) { right--; continue; }
        if ((a | 32) != (b | 32)) return false;
        left++;
        right--;
    }
    return true;
}

private static boolean isAlnumCode(int c) { return (c >= 48 && c <= 57) || ((c | 32) >= 97 && (c | 32) <= 122); }

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        int a = s.charAt(left);
        int b = s.charAt(right);
        if (!isAlnumCode(a)) { left++; continue; }
        if (!isAlnumCode(b)) { right--; continue; }
        if ((a | 32) != (b | 32)) return false;
        left++;
        right--;
    }
    return true;
}

def _is_alnum_code(c: int) -> bool: return 48 <= c <= 57 or 97 <= (c | 32) <= 122

def is_palindrome(s: str) -> bool:
    left = 0
    right = len(s) - 1
    while left < right:
        a = ord(s[left])
        b = ord(s[right])
        if not _is_alnum_code(a):
            left += 1
            continue
        if not _is_alnum_code(b):
            right -= 1
            continue
        if (a | 32) != (b | 32): return False
        left += 1
        right -= 1
    return True

const isAlnumCode = (c: number) => (c >= 48 && c <= 57) || ((c | 32) >= 97 && (c | 32) <= 122);

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    const a = s.charCodeAt(left);
    const b = s.charCodeAt(right);
    if (!isAlnumCode(a)) { left++; continue; }
    if (!isAlnumCode(b)) { right--; continue; }
    if ((a | 32) !== (b | 32)) return false;
    left++;
    right--;
  }
  return true;
}