DSA sheet · Strings · Two Pointers pattern

Valid Palindrome

This video opens the strings part of the sheet. The teacher reminds us that string questions mostly fall into just two patterns: two pointers and sliding window. The first two-pointer question on the sheet, Reverse a String, she skips because it is very easy, so she starts directly with Valid Palindrome. It matters because it is the cleanest example of "compare one character from the front with one from the back, then move both inwards". Valid Palindrome II, Longest Palindromic Substring and many others are built on this same move.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Two pointers from scratch (what you must know first)
• Part A · Brute force: clean, reverse and compare
• Part B · Optimal: two pointers from both ends
• Part C · Writing your own "is alphanumeric" check
• Part D · Revision page

Part 0 · Before starting: two pointers from scratch

What is a "pointer" here?

In Python we don't have real memory pointers. A pointer in these notes is simply an index, a whole number that says "I am looking at position i of the array or string". "Two pointers" means we keep two such indexes and move them by our own rules, instead of using two nested loops.

The brute force that two pointers replaces

Many array/string questions talk about pairs of positions (i, j). The simplest idea is to try every pair with two loops: about n × n / 2 pairs, so O(n²). For n = 10⁵ that is about 10¹⁰ steps, far past the rough limit of 10⁸ operations per second, so we get TLE (Time Limit Exceeded).

Two pointers works when something about the input lets us throw away many pairs without checking them. That "something" can be:

• sorted order: if the sum is too big, moving the right pointer left is the only way to make it smaller, so all pairs with the old right end can be skipped;
• the shape of the question: for a palindrome, position i only ever needs to be compared with its mirror position n − 1 − i. All other pairs are useless, so we never look at them.

The kinds of two pointers you'll meet in this notebook

Opposite-end pointers: which one moves, and why nothing is skipped

The rule of opposite-end pointers is: at each step, look at the two values, decide, then move one or both pointers inwards. The safety argument is always the same: the pair we give up on can never be part of the answer. For palindromes this is easy: once s[left] and s[right] have been compared, that pair is finished. No other pair uses these two mirror positions together, so we move both inwards and lose nothing.

Two pointers vs sliding window (the teacher's way to choose)

• Two pointers: we care about exactly two positions at a time, and nothing in between matters for that step. Here: "is the m at the front equal to the m at the back?" The characters between them don't matter yet.
• Sliding window: we care about everything between the two ends, a continuous block (a subarray or substring), like "the sum of this window".

A palindrome check compares two single points, so it is a two-pointer question.

Words used on this page

• Palindrome: a string that reads the same from left to right and from right to left, e.g. "apa", "racecar".
• Alphanumeric: a letter (a–z, A–Z) or a digit (0–9). "Alpha" = alphabet, "numeric" = number. Everything else (space, comma, colon, #, ?, _ …) is non-alphanumeric.
• Mirror position: for index i in a string of length n, the mirror is n − 1 − i (first ↔ last, second ↔ second last, …).

Part A · Brute force: clean, reverse and compare

LeetCode 125

1The question in simple words

You get a string s. Return True if it is a palindrome after two clean-up rules, otherwise False:

• Case doesn't matter: capital A and small a count as the same letter.
• Ignore everything that is not a letter or digit: spaces, commas, colons and other symbols are simply skipped.

The teacher walks through the Panama example by eye first: the capital A at the front and the small a at the end count as the same, so they match. Then there's a space, which we just step over. Then m and m match, a and a, n and n. Then there's a comma, so we step past it, then a space, so we step past that too, and only then compare the next a with its partner. We only compare when both sides are on a letter or digit.

2What the constraints tell us

• 1 ≤ s.length ≤ 2 × 10⁵ → at least one character, and n is large-ish. O(n) is clearly fine. O(n²) would be about 4 × 10¹⁰ steps, too slow.
• s has only printable ASCII characters → letters, digits, spaces and normal symbols. No strange Unicode, so str.isalnum() and str.lower() behave as expected.
• The teacher's reason for reading constraints: to know whether we need to optimise at all, and if yes, which optimisation will work.

3Intuition

The definition of a palindrome is "same forwards and backwards". So the most direct test is: write the string backwards and see if you get the same thing.

• "aman" backwards is "nama". Different → not a palindrome.
• "apa" backwards is "apa". a = a, p = p, a = a → palindrome.

4Building the logic

The teacher's brute force: take a second string s1, put the reverse of s in it, then compare the two strings one position at a time. If any position differs → False. If all positions agree → True.

5Approach steps

1. Build clean: go through s, keep a character only if it is alphanumeric, and store it in lowercase.
2. Build rev = clean reversed (this is the extra copy, the teacher's s1).
3. For every index i, if clean[i] != rev[i] → return False.
4. If the loop finishes → return True.

6Code (Python)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        clean = [ch.lower() for ch in s if ch.isalnum()]   # letters/digits only, lowercase
        rev = clean[::-1]                                  # the reversed copy (s1)
        for i in range(len(clean)):
            if clean[i] != rev[i]:
                return False
        return True

7Code line by line

8Dry run (hand table)

s = "race a car" → clean = r a c e a c a r, rev = r a c a e c a r.

For the Panama string, clean = rev = amanaplanacanalpanama, all 21 positions agree, so the answer is True.

9Complexity & remember

• Time O(n): the teacher counts it as about 2n, n to copy/reverse into s1 and n more to compare. 2n is still linear.
• Space O(n): the extra copies.
• Will it pass? Yes. With n = 2 × 10⁵, 2n is tiny. Her point: if n were as large as 10⁹, even this would be too slow and too big. And in an interview, two follow-ups are common: "can you make it faster?" and "you're not allowed extra space". Both push us to two pointers.

Part B · Optimal: two pointers from both ends

1The question again, with the new goal

Same question. New goal: no extra string (O(1) extra space) and only one pass over the characters.

2Choosing the pattern

When we want to optimise a string problem, we pick from the two string patterns. At each step we need to compare two single points (front character, back character) and nothing in between. That's two pointers, not sliding window (see Part 0).

3Intuition: two fingers walking towards each other

Put your left finger on the first character and your right finger on the last. Instead of making a reversed copy, read the "backwards" string directly with the right finger.

• If a finger is on a space or a symbol, step over it (left finger forward, right finger backward).
• When both fingers are on letters/digits, compare them ignoring case.
• Different → not a palindrome, stop right away.
• Same → this pair is done. Move both fingers one step inwards and repeat.
• When the fingers meet or cross, every pair has matched → palindrome.

4Building the conditions, the way the teacher does

Condition 1: one match doesn't mean "palindrome"

Suppose s[left] and s[right] are equal. Can we return True? No. A palindrome needs every mirror pair to match, not just one. So on a match we only move the pointers and keep checking.

But one mismatch is enough to say False. For example, if one side shows p and the other shows a, it's over. So the teacher's tip is: look for the False case inside the loop; return True only after the loop, once no mismatch was found.

Condition 2: when should the loop stop? left < right

The pointers move towards the middle. At some point they cross (left goes past right). After that we'd only be comparing pairs we have already checked, so we must stop.

Condition 3: skip anything that isn't a letter or digit

Before comparing, each pointer must be on an alphanumeric character.

• If s[left] is not alphanumeric → left += 1 and go round the loop again.
• Else, if s[right] is not alphanumeric → right -= 1 and go round again.
• Else (both are alphanumeric) → now we may compare.

Python has the built-in str.isalnum() for this (Java has Character.isLetterOrDigit, C++ has isalnum). If you forget it in an interview, you can write your own (Part C).

Condition 4: compare in the same case

The first comparison in the Panama string is 'A' vs 'a'. As raw characters they're different, but the question says they are the same. We don't know which side might be uppercase, so we convert both to lowercase: s[left].lower() != s[right].lower() → return False.

Condition 5: on a match, move both

If they're equal, left += 1 (forward) and right -= 1 (backward), and the loop checks the next pair.

5Approach steps

1. left = 0, right = len(s) - 1.
2. While left < right:
3.   if s[left] is not alphanumeric → move left forward;
4.   else if s[right] is not alphanumeric → move right backward;
5.   else if their lowercase forms differ → return False;
6.   else → move both inwards.
7. After the loop → return True.

6Code (Python)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():          # left is on a space/symbol
                left += 1
            elif not s[right].isalnum():       # right is on a space/symbol
                right -= 1
            elif s[left].lower() != s[right].lower():
                return False                   # a real mismatch
            else:                              # matched pair
                left += 1
                right -= 1
        return True

7Code line by line

8Dry run

s = "A man, a plan, a canal: Panama" (30 characters, index 0 to 29). ␣ = a space.

Yellow = where the pointers are now. Grey = already finished (matched or skipped).

Every round, step by step:

Notice the middle c is never compared. It's its own mirror, which is exactly the < vs <= point.

A False example: "race a car"

9Complexity & remember

• Time O(n): the two pointers start at the two ends and meet around the middle. The teacher calls it about n/2 comparisons, which is O(n). Skipped symbols add at most one round each, so it's still linear. Nothing is copied.
• Space O(1): just two integers. This is what makes it better than Part A.
• On LeetCode this ran as the fastest solution in her submission.

Part C · Writing your own "is alphanumeric" check

The teacher's interview tip: every language has a built-in for this (isalnum in Python and C++, isLetterOrDigit in Java). If you forget its name in an interview, don't panic. Write a tiny helper yourself.

1The idea

Every character has a number code (its ASCII value, which Python gives with ord(ch)). Letters and digits sit in three continuous ranges:

So a character is alphanumeric if it falls inside any of the three ranges. In Python you can compare characters directly ('a' <= ch <= 'z'), which compares their codes for you.

2Code (Python)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        def is_alnum(ch):
            return ('a' <= ch <= 'z') or ('A' <= ch <= 'Z') or ('0' <= ch <= '9')

        left, right = 0, len(s) - 1
        while left < right:
            if not is_alnum(s[left]):
                left += 1
            elif not is_alnum(s[right]):
                right -= 1
            elif s[left].lower() != s[right].lower():
                return False
            else:
                left += 1
                right -= 1
        return True

3Line by line, complexity

The helper does at most 6 comparisons, so it costs O(1) per call. The whole solution stays O(n) time, O(1) space.

Part D · Revision page

s = Solution()
print(s.isPalindrome("A man, a plan, a canal: Panama"))  # True
print(s.isPalindrome("race a car"))                      # False
print(s.isPalindrome(" "))                               # True  (nothing to compare)
print(s.isPalindrome(".,:"))                             # True
print(s.isPalindrome("0P"))                              # False (digit 0 vs letter p)
print(s.isPalindrome("aA"))                              # True

Based on this video: Valid Palindrome | Two Pointers