Skip to content

Volume ITechnology

4.5.1 — Valid Palindrome ​

LeetCode 125 · Easy · ★ Blind 75

The problem ​

You are given a string s. Return true if it is a palindrome, and false if it is not. A palindrome reads the same forwards and backwards, like "level" or "noon". For this problem, two extra rules apply.

  1. Ignore upper and lower case. A and a count as the same letter.
  2. Ignore every character that is not a letter or a digit. Spaces, commas, colons and so on are simply skipped.
s = "A man, a plan, a canal: Panama"  →  true
s = "race a car"                      →  false
s = " "                               →  true

The first example becomes "amanaplanacanalpanama" once the junk is removed and everything is lowercase, and that reads the same both ways. The second becomes "raceacar", which reversed is "racaecar", so it is not a palindrome. The third has no letters or digits left at all. An empty string reads the same both ways, so the answer is true.

The string can have up to 200,000 characters.

What the problem is really asking ​

A string is a palindrome when its first character matches its last, its second matches its second-to-last, and so on, all the way to the middle. So the real question is: "do the characters match in pairs, working inwards from both ends?" The only twist is that some characters do not count and must be skipped.

The brute force, and where it wastes memory ​

Build a clean copy of the string, with only lowercase letters and digits. Then compare the copy with its reverse.

python
def isPalindrome(s):
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

c.isalnum() is True when c is a letter or a digit. cleaned[::-1] is Python's way of writing "the string reversed". This is short, correct, and a fine first answer.

It is already O(n) time, so speed is not the problem. The waste is memory: it builds two new strings, the cleaned copy and its reverse, each as long as the input. If the string were a gigabyte, you would need two more gigabytes.

The idea ​

Do not build any copies. Put one finger at the start of the string and one at the end. Call them l for left and r for right. Then repeat:

  1. If the left finger is on a junk character, move it right until it lands on a letter or digit.
  2. Do the same for the right finger, moving it left.
  3. Compare the two characters, ignoring case. If they differ, it is not a palindrome.
  4. If they match, move both fingers one step inward and repeat.

When the fingers meet or cross, every pair has matched, so it is a palindrome.

The solution ​

python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1                         # (1)
        while l < r:                                 # (2)
            while l < r and not s[l].isalnum():      # (3)
                l += 1
            while l < r and not s[r].isalnum():      # (4)
                r -= 1
            if s[l].lower() != s[r].lower():         # (5)
                return False
            l += 1                                   # (6)
            r -= 1
        return True                                  # (7)
ts
function isPalindrome(s: string): boolean {
  const ok = (c: string) => /[a-z0-9]/i.test(c);   // letter or digit?
  let l = 0, r = s.length - 1;                     // (1)
  while (l < r) {                                  // (2)
    while (l < r && !ok(s[l])) l++;                // (3)
    while (l < r && !ok(s[r])) r--;                // (4)
    if (s[l].toLowerCase() !== s[r].toLowerCase()) {  // (5)
      return false;
    }
    l++;                                           // (6)
    r--;
  }
  return true;                                     // (7)
}

Line by line ​

(1) Place the two pointers. l starts at the first position, 0. r starts at the last position, len(s) - 1. We subtract 1 because positions start counting at 0, so a string of length 5 has positions 0 to 4.

(2) Keep going while the pointers have not met. When l and r meet or cross, every pair has been checked. If the string has an odd number of real characters, the middle one is left alone. That is fine, because a single character always matches itself.

(3) Skip junk on the left. While the character at l is not a letter or digit, move l one step right. TypeScript has no isalnum, so we write a tiny helper, ok, using a regular expression. A regular expression is a short pattern for matching text. /[a-z0-9]/i means "one character from a to z or 0 to 9", and the i at the end means "ignore case".

(4) Skip junk on the right, moving r one step left.

The check l < r inside lines (3) and (4) is easy to forget, and it matters. Take the string ",,,", which is all junk. Without the check, line (3) would keep moving l right, past the end of the string, and the program would crash. With the check, l stops when it reaches r. The outer loop then ends, and we return true.

(5) Compare, ignoring case. .lower() turns both characters into lowercase, so A and a compare as equal. If they still differ, the string is not a palindrome, and we return false immediately.

(6) Move both pointers inward. This pair matched, so we step past both characters to the next pair.

(7) Every pair matched. The string is a palindrome.

Trace ​

Take s = "A, ba". The positions are: 0 A, 1 ,, 2 (a space), 3 b, 4 a.

Roundl startr startAfter skipping junkCompareResult
104l=0 (A), r=4 (a)a vs amatch, move to 1 and 3
213l skips , and space → 3; r=3loop ends, l is not less than r—

The outer loop stops because l and r are both at 3. We return true. The cleaned string is "aba", which is a palindrome.

Complexity, derived ​

Time. l only ever moves right, and r only ever moves left. Between them they can cross the string at most once, so together they take at most n steps. Each step does a constant amount of work. So the time is O(n).

The loops inside the loop do not make this O(n^2). They do not restart from the beginning. They just move the same two pointers further along, and the pointers never move back.

Space. We only keep two numbers, l and r. That does not grow with the string, so the extra memory is O(1). This is the whole reason to prefer this version over the cleaned-copy version.

Edge cases ​

  • Only junk, such as " " or ",,,". The inner loops stop at the meeting point, and the answer is true.
  • One character. l and r both start at 0, so the outer loop never runs. A single character is a palindrome.
  • Digits matter. "0P" compares 0 with p, which differ, so the answer is false. Do not skip digits.
  • Mixed case, such as "Aa". Lowercasing makes them equal, so the answer is true.

Variations you will meet ​

  • Valid Palindrome II. You may delete at most one character. When the two pointers disagree, try skipping the left character, and also try skipping the right one. If either of the two remaining stretches is a palindrome, the answer is true.
  • Longest Palindromic Substring and Palindromic Substrings. Instead of moving inward from the ends, you start from each possible middle and move outward. See 4.23.5.
  • Reverse a string in place. The same two pointers, swapping instead of comparing.

The general lesson: when a question compares the two ends of a sequence, put one pointer at each end and walk them toward each other.

What the interviewer will push on ​

"Can you do it without extra memory?" They want the pointer version, and the reason: two pointers skip junk where it stands, so no copies are needed.

"What happens on a string of only punctuation?" They are checking the l < r guard in the inner loops. Without it, the pointer runs off the end.

"Why don't the inner loops make it O(n^2)?" Because neither pointer ever moves backwards. They take at most n steps between them, in total.

"What about Unicode letters, like é?" Python's isalnum already accepts them. The TypeScript pattern [a-z0-9] does not, so you would use /[\p{L}\p{N}]/u, which means "any letter or any digit in any language".

One thing to volunteer: offer the two-line cleaned-copy version first, because it is clear. Then offer the pointer version when memory comes up. Showing both, and the trade between them, is better than jumping to the clever one.

Next: 4.5.2 Two Sum II. The same two pointers, but now we must prove which pointer should move.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet