Two Pointers on Strings

A quick connection

In Chapter 1.1 you used two pointers walking toward each other to find pairs in a sorted array. In Chapter 1.2 you used two pointers walking in the same direction to merge or copy. Those skeletons work unchanged on strings — a string is just an array of characters.

This chapter is deliberately short. The patterns are the same; the only newness is recognising string-flavoured problem statements as two-pointer problems, and handling two small string-specific gotchas (case, non-alpha characters).

Pattern A — Opposite direction: palindrome check

The skeleton

left, right = 0, len(s) - 1
while left < right:
    if s[left] != s[right]:
        return False          # mismatch found
    left  += 1
    right -= 1
return True

Valid Palindrome (LC #125) — ignore non-alphanumeric, ignore case

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left  += 1        # skip non-alphanumeric from left
        while left < right and not s[right].isalnum():
            right -= 1        # skip non-alphanumeric from right
        if s[left].lower() != s[right].lower():
            return False
        left  += 1
        right -= 1
    return True

Frame-by-frame: "A man, a plan, a canal: Panama"

After stripping non-alpha in-place (conceptually):
"amanaplanacanalpanama"

left=0 'a', right=19 'a' → match, advance
left=1 'm', right=18 'm' → match, advance
left=2 'a', right=17 'a' → match, advance
...
All characters match → True ✅

Pattern B — Same direction: is subsequence

A subsequence of string t is a string s whose characters appear in t in the same order but not necessarily consecutively. "ace" is a subsequence of "abcde"; "aec" is not.

The skeleton

i, j = 0, 0                      # i → s, j → t
while i < len(s) and j < len(t):
    if s[i] == t[j]:
        i += 1                    # matched one more character of s
    j += 1                        # always advance through t
return i == len(s)                # did we consume all of s?

Frame-by-frame: s = "ace", t = "abcde"

i=0 j=0: s[0]='a' == t[0]='a' → match, i=1, j=1
i=1 j=1: s[1]='c' != t[1]='b' → no match, j=2
i=1 j=2: s[1]='c' == t[2]='c' → match, i=2, j=3
i=2 j=3: s[2]='e' != t[3]='d' → no match, j=4
i=2 j=4: s[2]='e' == t[4]='e' → match, i=3, j=5
i=3 → i == len(s) → True ✅

O(n) time, O(1) space — no extra array, no sorting, single pass.

Pattern C — Two-string comparison: merge/align

Some problems give you two strings and ask you to compare them character by character, skipping or inserting characters. These use two separate pointers, one per string.

Backspace String Compare (LC #844)

Given two strings where # means backspace, check if they produce the same result after processing.

def backspaceCompare(s: str, t: str) -> bool:
    i, j = len(s) - 1, len(t) - 1
    skip_s = skip_t = 0

    while i >= 0 or j >= 0:
        # find the next valid character in s
        while i >= 0:
            if s[i] == '#':
                skip_s += 1
                i -= 1
            elif skip_s > 0:
                skip_s -= 1
                i -= 1
            else:
                break

        # find the next valid character in t
        while j >= 0:
            if t[j] == '#':
                skip_t += 1
                j -= 1
            elif skip_t > 0:
                skip_t -= 1
                j -= 1
            else:
                break

        # compare the two valid characters
        if i >= 0 and j >= 0:
            if s[i] != t[j]:
                return False
        elif i >= 0 or j >= 0:
            return False             # one string has extra characters

        i -= 1
        j -= 1

    return True

Why scan from the right? Because # deletes the character to its left. Scanning right-to-left lets us count pending backspaces and skip the correct number of characters without building a new string.

O(n + m) time, O(1) space — superior to the O(n) space approach of building both result strings and comparing.

The one idea to remember

Where to spot this pattern

Trigger words:

• "palindrome" or "reads the same forwards and backwards"
• "subsequence" — is one string hidden in another in order?
• "after processing / simulating" — backspace, delete, skip
• "compare two strings" ignoring certain characters
• "reverse the string" — setup for palindrome or reversal trick (Chapter 3.7)

5 disguises:

1. Valid Palindrome (LC #125): skip non-alphanumeric; case-insensitive.
2. Valid Palindrome II (LC #680): allowed to delete at most one character — try skipping left or right on first mismatch.
3. Is Subsequence (LC #392): same-direction classic.
4. Backspace String Compare (LC #844): dual right-to-left with skip counters.
5. Long Pressed Name (LC #925): same-direction, allow repeated characters in typed string.

Common traps

Complexity

Say it like a pro (interview one-liner)

"This is a two-pointer problem on a string. For palindromes, I walk inward from both ends comparing characters. For subsequences, I use one pointer per string advancing together. All variants run in O(n) time and O(1) space — no extra array needed."

left, right = 0, len(s) - 1
while left < right:
    skip non-alphanumeric, compare s[left].lower() vs s[right].lower()
    if mismatch → False; else advance both
return True

i, j = 0, 0
while i < len(s) and j < len(t):
    if s[i] == t[j]: i += 1
    j += 1
return i == len(s)

Check yourself

Practice problems

Next up: Sliding Window on Strings — maintaining a character frequency map inside a moving window to find minimum windows, permutation matches, and anagram occurrences.