Valid Palindrome: hai con trỏ đọc từ hai đầu vào

"A man, a plan, a canal: Panama" — làm sạch nó, lật ngược lại, nó đọc y chang. Đó là toàn bộ bài toán. LeetCode 125 yêu cầu kiểm tra palindrome trên chuỗi có thể chứa dấu câu, khoảng trắng, và hỗn hợp chữ hoa thường. Ràng buộc thú vị là cái không xuất hiện trong đề bài: làm điều đó mà không tạo thêm một string thứ hai.

Constraints buộc ta phải làm gì

Chuỗi có thể dài tới 200 000 ký tự và chỉ chứa printable ASCII. Từ đó rút ra ngay hai điểm.

O(n) time là sàn tối thiểu — bạn phải đọc mọi ký tự ít nhất một lần trong trường hợp xấu nhất. Bất kỳ approach O(n²) nào đều chết ngay từ đầu với kích thước đó. Printable ASCII có nghĩa là không bao giờ gặp các edge case Unicode như ký tự multi-byte hay combining diacritics. Kiểm tra isalnum và một lần lowercase là đủ; không cần Unicode normalization.

Ràng buộc về space mới là thứ thực sự phân biệt các approach. Bài toán không nêu rõ, nhưng s.length tới 200 000 có nghĩa là allocation một bản cleaned copy rồi một bản đảo ngược của nó tốn tới 400 000 ký tự bộ nhớ — mà bạn chỉ đọc qua một lần rồi bỏ. Toàn bộ allocation đó tồn tại chỉ vì bạn chọn vật chất hoá thứ có thể tính on the fly. Nhận ra điều đó là cả trò chơi ở đây.

Brute force: làm sạch trước, so sánh bản đảo ngược

Phản xạ đầu tiên là lọc chuỗi, lowercase hết, rồi so sánh với bản đảo ngược. Dễ viết và dễ đọc.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = ""
        for char in s:
            if char.isalnum():
                cleaned += char.lower()
        return cleaned == cleaned[::-1]

using System.Text;
 
public class Solution {
    public bool IsPalindrome(string s) {
        var cleaned = new StringBuilder();
        foreach (char c in s) {
            if (char.IsLetterOrDigit(c))
                cleaned.Append(char.ToLower(c));
        }
        string cleanedStr = cleaned.ToString();
        char[] reversed = cleanedStr.ToCharArray();
        Array.Reverse(reversed);
        return cleanedStr == new string(reversed);
    }
}

O(n) time — tối đa hai lần duyệt. Nhưng cần O(n) space cho cleaned và thêm O(n) cho bản đảo ngược. Trên input 200 000 ký tự, đó là tới 400 000 ký tự allocation chỉ để đọc qua một lần. Bản đảo ngược không làm gì ngoài việc cho bạn một comparison target — thứ bạn hoàn toàn có thể tính được mà không cần vật chất hoá nó.

Approach này chạy đúng. Trong một script hay tool dùng một lần, tôi sẽ viết vậy và đi tiếp. Nhưng kiểm tra palindrome không cần hai string — nó cần một phép so sánh đối xứng. Đó là việc của two pointers.

Nước đi tối ưu: đọc từ hai đầu vào

Đặt một con trỏ ở đầu trái và một ở đầu phải của chuỗi. Đi chúng về phía nhau. Ở mỗi bước, skip bất kỳ ký tự nào không phải alphanumeric — cả hai con trỏ làm độc lập trước khi so sánh. Nếu các ký tự chúng đứng trên không khớp (case-insensitive), trả về false. Nếu hai con trỏ vượt qua nhau mà không có mismatch, trả về true.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, 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

public class Solution {
    public bool IsPalindrome(string s) {
        int left = 0, right = s.Length - 1;
 
        while (left < right) {
            while (left < right && !char.IsLetterOrDigit(s[left]))
                left++;
            while (left < right && !char.IsLetterOrDigit(s[right]))
                right--;
 
            if (char.ToLower(s[left]) != char.ToLower(s[right]))
                return false;
 
            left++;
            right--;
        }
 
        return true;
    }
}

O(n) time, O(1) space. Mỗi ký tự được thăm tối đa một lần — hai vòng while lồng nhau thực ra không lồng nhau theo nghĩa big-O. left và right chỉ chuyển động về phía nhau, nên toàn bộ quá trình thực thi cả hai vòng while con cộng lại tốn tối đa n lần lặp. Không có gì được allocation. Không có string thứ hai.

Trace qua ví dụ từng bước

Lấy s = "A man, a plan, a canal: Panama". Chuỗi có 30 ký tự (index 0-29).

Từng bước cho vài lần đầu:

Khoi dau: left=0  ('A'),  right=29 ('a')
          s[0].lower() == s[29].lower()  ->  'a' == 'a'  ->  khop
          left=1, right=28

Buoc 2:   left=1  (' ')  -> khong phai alphanumeric, skip -> left=2
          right=28 ('m') -> alphanumeric, dung lai
          s[2].lower() == s[28].lower()  ->  'm' == 'm'  ->  khop
          left=3, right=27

Buoc 3:   left=3  ('a'), right=27 ('a')
          'a' == 'a'  ->  khop
          left=4, right=26

Buoc 4:   left=4  ('n'), right=26 ('n')
          'n' == 'n'  ->  khop
          left=5, right=25

Buoc 5:   left=5  (',') -> skip -> left=6 (' ') -> skip -> left=7 ('a')
          right=25 ('a') -> khop
          left=8, right=24

... cac con tro tiep tuc hoi tu ...

left >= right: vong lap thoat, return True

Bây giờ so với s = "race a car":

left=0 ('r'), right=9 ('r')   ->  khop   left=1, right=8
left=1 ('a'), right=8 (' ')   ->  skip right -> right=7 ('a')
              right=7 ('a')   ->  'a' == 'a'  ->  khop   left=2, right=6
left=2 ('c'), right=6 ('a')   ->  'c' != 'a'  ->  return False

Ba lần so sánh thay vì tám. Đó là early exit trong thực tế — brute force luôn đọc hết ký tự rồi mới quyết định; two pointers thoát ngay khi tìm thấy mismatch đầu tiên.

Guard condition không được bỏ sót

Guard left < right bên trong cả hai vòng while con quan trọng hơn trông có vẻ. Nếu không có nó, khi toàn bộ chuỗi là non-alphanumeric — ví dụ "!!!" — left skip qua index 2 và kết thúc ở 3, còn right skip xuống dưới 0. Điều kiện vòng ngoài sẽ bắt được chuyển động đầu tiên nhưng không bắt được overrun của vòng skip. Thiếu một guard, một lần index-out-of-bounds. Tôi giờ viết cả hai guard theo phản xạ; chi phí là hai phép so sánh thêm mỗi lần lặp, và đảm bảo correctness xứng đáng mỗi cái trong số đó.

Edge cases và lý do code xử lý được từng cái

Toàn ký tự non-alphanumeric — " " hay ".,!": cả hai con trỏ skip cho đến khi left >= right và vòng while ngoài không bao giờ thực hiện một phép so sánh nào. Trả về true. Đúng: bài toán nói chuỗi rỗng sau khi strip là palindrome hiển nhiên, và " " strip thành rỗng.

Một ký tự alphanumeric duy nhất — "a": left == right == 0, nên left < right là false ngay lập tức. Trả về true mà không vào vòng lặp. Một ký tự luôn là gương của chính nó.

Toàn chữ hoa — "ABCCBA": skip logic không bao giờ kích hoạt vì mọi ký tự đều là alphanumeric. .lower() trên cả hai phía chuẩn hoá trước khi so sánh. Không cần case đặc biệt; conversion được áp dụng vô điều kiện.

Hỗn hợp chữ và số — "A1B2b1a": các số là alphanumeric và tham gia so sánh như chữ cái. '1' phải bằng '1', '2' phải bằng '2'. Chuỗi này tình cờ là palindrome (a1b2b1a sau khi lowercase), nên trả về true.

Bẫy case-sensitivity — 'A' với 'a': lỗi phổ biến nhất với bài này là so sánh ký tự trước khi lowercase. 'A' != 'a' trong phép so sánh char thô. Cả hai phía phải qua .lower() / char.ToLower() trước khi kiểm tra !=. Code làm điều này vô điều kiện ở mỗi bước so sánh.

So sánh các approach

Cả hai đều O(n) time. Sự khác biệt về space mới là câu chuyện chính. Trong môi trường hạn chế bộ nhớ — embedded systems, streaming pipelines, input rất lớn — O(n) so với O(1) là khoảng cách thật. Trong phỏng vấn, nó là tín hiệu cho thấy bạn hiểu hình dạng thực sự của bài toán.

Nhận diện pattern và mental model

Two-pointer inward walk là phản xạ đúng khi bạn thấy:

• "reads the same forward and backward" — phép so sánh đối xứng từ hai đầu
• "ignore case" kết hợp "alphanumeric only" — skip-and-filter inner loop
• "kiểm tra tính đối xứng" trên sequence tuyến tính — hai đầu đi vào giữa
• ràng buộc space ngụ ý hoặc tường minh với input lớn

Skip logic — while (not valid): advance — là phần có thể tái sử dụng. Bất cứ khi nào two-pointer walk cần bỏ qua một số phần tử nhất định, cái while bên trong đó là pattern đúng. Guard left < right bên trong nó là bắt buộc.

Approach nào tôi sẽ dùng

Two pointers. Không phải vì lợi thế early exit lúc nào cũng đáng kể — trên chuỗi ngẫu nhiên thường không. Mà vì O(1) space về mặt cấu trúc tốt hơn: thuật toán không cần biết gì về chuỗi ngoài những gì đang ở vị trí con trỏ hiện tại. Nó là fit tự nhiên cho phép kiểm tra đối xứng. Brute force hoạt động bằng cách giải một bài toán con khác — "làm sao kiểm tra equality trên một derived string?" — và việc derive đó là overhead không cần thiết.

Trong production codebase nơi function được gọi hàng triệu lần trên input lớn, O(1) space loại bỏ GC pressure. Trong phỏng vấn, tôi viết two pointers thẳng và giải thích lợi thế space. Brute force hữu ích như một thought experiment để xác nhận hiểu bài toán, không phải như một candidate solution.

Các bài anh em

Đây là entry point cho họ two-pointer. Pattern mở rộng tự nhiên:

• Two Sum II — Input Array Is Sorted (167): cùng cái inward walk trên mảng đã sort, nhưng thay vì kiểm tra equality bạn kiểm tra xem tổng có khớp target không. Skip logic biến mất; pointer movement trở nên điều kiện theo hướng của tổng.
• Valid Palindrome II (680): cho phép xóa tối đa một ký tự. Chạy cùng cái two-pointer walk; khi gặp mismatch, thử skip left hoặc right và kiểm tra phần còn lại có là palindrome không. Logic cơ sở ở đây là dependency trực tiếp.
• 3Sum (15): fix một phần tử, chạy two-pointer search trên phần còn lại. Đây là Two Sum II nhúng bên trong outer loop — inward walk hoàn toàn giống nhau.
• Container With Most Water (11): two pointers ở hai đầu mảng height, mỗi bước di chuyển cạnh thấp hơn vào trong. Cùng skeleton, quy tắc quyết định khác ở mỗi bước.
• Palindrome Linked List (234): tìm midpoint, đảo ngược nửa sau, rồi so sánh bằng two pointers. Phase so sánh là cùng cái walk bạn đã viết ở đây, áp dụng cho linked list.

Valid Palindrome dạy bạn cái phản xạ: hai đầu, đi vào trong, xử lý điều kiện skip với guard left < right, thoát ngay khi mismatch đầu tiên. Mọi bài trong danh sách này là phản xạ đó được áp dụng cho một quyết định khó hơn ở mỗi bước.