Chương 2 - String

Chuỗi thực ra là mảng các ký tự - tất cả kỹ thuật ở Chương 1 (two pointers, in-place, prefix) đều áp dụng được. Tuy nhiên, string có 2 đặc thù riêng: (i) phải xử lý bảng mã (chỉ ASCII hay full Unicode?), và (ii) trong Python, chuỗi là immutable - không sửa được tại chỗ, mọi thao tác “đổi ký tự” thực ra phải chuyển sang list rồi ''.join.

Mục tiêu chương

Sau chương này, bạn sẽ:

• Phân biệt các giả thiết về ký tự: ASCII / Unicode / chỉ alphanumeric / phân biệt hoa thường.
• Thuộc 3 mẫu chính: counting, two pointers, parsing.
• Hiểu vì sao string immutable trong Python → khi nào phải chuyển sang list.
• Biết cách gateway sang Sliding Window (Ch 27), KMP (Ch 35), Rolling Hash (Ch 34).

Khi nào dùng pattern này?

• Đề bài thao tác trên một / nhiều chuỗi: kiểm tra palindrome, anagram, đảo từ, parse số, …
• Đa số bài Easy/Medium chỉ cần thuần kỹ thuật two pointers, Counter, state machine.
• Bài Medium/Hard về string thường sẽ dùng pattern nâng cao: Sliding Window (Chương 27), Trie (Chương 23), Rolling Hash (Chương 34), KMP (Chương 35).
• Khi nhận đề luôn hỏi 3 câu:
  1. Chỉ ASCII (256 ký tự, 26 chữ cái) hay full Unicode?
  2. Phân biệt hoa/thường không? Có dấu cách ở đầu/cuối không?
  3. Chuỗi có thể rỗng không?

Template code

from collections import Counter
from typing import List

def two_pointers_in_string(s: str) -> bool:
    """Mẫu two pointers: kiểm tra điều kiện đối xứng / cặp."""
    l, r = 0, len(s) - 1
    while l < r:
        if not check(s[l], s[r]):
            return False
        l += 1
        r -= 1
    return True


def count_chars(s: str) -> dict[str, int]:
    """Bảng đếm ký tự - gần như mọi bài string đều dùng."""
    return Counter(s)

Bài tự luyện cuối chương

• LC 28 - Find the Index of the First Occurrence in a String
• LC 58 - Length of Last Word
• LC 67 - Add Binary
• LC 415 - Add Strings
• LC 387 - First Unique Character in a String
• LC 383 - Ransom Note
• LC 344 - Reverse String
• LC 541 - Reverse String II

---

2.1 Valid Anagram (LC 242)

Đề bài

Cho hai chuỗi s và t. Trả về True nếu t là anagram của s (cùng các ký tự, cùng số lần xuất hiện, chỉ khác thứ tự), ngược lại False.

Ví dụ

Input:  s = "anagram", t = "nagaram"
Output: True

Input:  s = "rat", t = "car"
Output: False

Ràng buộc

• 1 <= len(s), len(t) <= 5·10^4
• s, t chỉ chứa chữ thường tiếng Anh.

Clarifying questions

• Phân biệt hoa thường không? → Theo đề là chữ thường. Nếu hỗn hợp, nên hỏi rõ.
• Có Unicode (tiếng Việt có dấu, emoji) không? → Mặc định: ASCII. Follow-up Unicode sẽ thay bảng đếm 26 phần tử bằng Counter.
• Khoảng trắng có tính không? → Trong LC: tính. Nhưng bài “Valid Anagram of Sentence” có thể bỏ qua.

Hướng tiếp cận

Brute force - sắp xếp, O(n log n). sorted(s) == sorted(t). Code 1 dòng, nhưng O(n log n) về thời gian và O(n) về bộ nhớ (vì sorted trả về list).

Tối ưu - Counter một lượt, O(n). Đếm ký tự trong s, sau đó duyệt t và trừ. Nếu có ký tự nào âm hoặc kết thúc với mọi count = 0 → đúng anagram.

Tối ưu hơn nữa - bảng cố định 26 phần tử, O(1) extra space (theo bảng mã). Vì chỉ có 26 chữ cái, ta dùng int[26] (hoặc list 26 phần tử) thay cho dict. Bộ nhớ thực tế là O(1) (không phụ thuộc n).

Code Python 3

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return Counter(s) == Counter(t)


class SolutionFast:
    """Bảng cố định 26 chữ cái - O(1) bộ nhớ thực tế."""
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        for ch in t:
            count[ord(ch) - ord('a')] -= 1
            if count[ord(ch) - ord('a')] < 0:
                return False
        return True

Phân tích độ phức tạp

• Thời gian: O(n) cho cả 2 cách Counter / bảng 26.
• Bộ nhớ: O(1) (chính xác là O(k) với k = kích thước bảng chữ).
• Cách sort: O(n log n) time, O(n) space.

Bình luận

• Bẫy thường gặp:
  • Quên check độ dài trước - sẽ trả về True sai khi len(s) != len(t).
  • Dùng set(s) == set(t) - sai! Set bỏ đi count, “aab” và “ab” sẽ ra True.
• Follow-up phổ biến:
  1. Unicode → dùng Counter, không thể dùng bảng 26.
  2. Bài LC 49 (Group Anagrams) - gom các từ là anagram của nhau (xem bài 2.5).
  3. Bài LC 438 (Find All Anagrams in a String) - sliding window (Chương 27).
• Mẹo phỏng vấn: trình bày giải pháp Counter trước (gọn gàng, chỉ 1 dòng), sau đó mới nhắc đến giải pháp dùng mảng đếm 26 phần tử khi interviewer hỏi về tối ưu bộ nhớ.

Bài tự luyện liên quan

• LC 49 - Group Anagrams.
• LC 438 - Find All Anagrams in a String.
• LC 383 - Ransom Note.

---

2.2 Valid Palindrome (LC 125)

Đề bài

Cho chuỗi s. Coi là palindrome nếu sau khi chuyển toàn bộ chữ in hoa → thường và bỏ tất cả ký tự không phải chữ-và-số thì chuỗi đọc xuôi và ngược giống nhau. Trả về True / False.

Ví dụ

Input:  s = "A man, a plan, a canal: Panama"
Output: True
Giải thích: sau lọc → "amanaplanacanalpanama" - đọc xuôi và ngược giống nhau.

Input:  s = "race a car"
Output: False
Giải thích: sau lọc → "raceacar" - không palindrome.

Input:  s = " "
Output: True
Giải thích: chuỗi rỗng coi là palindrome.

Ràng buộc

• 1 <= len(s) <= 2·10^5
• s chứa chữ in hoa, in thường, số, và các ký tự khác.

Clarifying questions

• “Chữ-và-số” là gì? → Là chữ cái Latin (a–z, A–Z) hoặc số (0–9). Các ký tự khác như dấu cách, dấu chấm, ký tự đặc biệt đều bỏ qua.
• Chuỗi rỗng sau khi lọc có là palindrome không? → Có (quy ước LC).
• Phải xử lý Unicode không? → Mặc định LC chỉ ASCII.

Hướng tiếp cận

Brute force - lọc rồi so sánh đảo ngược - O(n) time, O(n) space. filtered = ''.join(ch.lower() for ch in s if ch.isalnum()), rồi filtered == filtered[::-1]. Đơn giản, nhưng tốn O(n) bộ nhớ phụ.

Tối ưu - Two pointers in-place - O(n) time, O(1) space. Hai con trỏ l (đầu) và r (cuối), bỏ qua ký tự không phải alphanumeric ở mỗi bên, rồi so sánh s[l].lower() == s[r].lower(). Nếu khác → False.

Code Python 3

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

Phân tích độ phức tạp

• Thời gian: O(n) - mỗi ký tự duyệt tối đa 1 lần.
• Bộ nhớ: O(1).

Bình luận

• Bẫy thường gặp:
  • Quên check l < r trong vòng while inner → out of range.
  • Quên .lower() khi so sánh → “Aa” sẽ bị False.
  • Dùng isalpha() thay vì isalnum() → bỏ sót chữ số.
• Follow-up phổ biến:
  1. LC 680 - Valid Palindrome II: cho phép xoá tối đa 1 ký tự. Hint: khi gặp mismatch, thử bỏ s[l] hoặc s[r], kiểm tra phần còn lại.
  2. LC 5 - Longest Palindromic Substring: expand từ tâm hoặc DP/Manacher.
  3. LC 9 - Palindrome Number: không được chuyển sang string.
• Tip: Two pointers trên string là kỹ thuật bạn sẽ dùng đi dùng lại - luôn nhớ phải check l < r cẩn thận khi có vòng while bên trong.

Bài tự luyện liên quan

• LC 680 - Valid Palindrome II.
• LC 5 - Longest Palindromic Substring.
• LC 9 - Palindrome Number.

---

2.3 Longest Common Prefix (LC 14)

Đề bài

Cho mảng các chuỗi strs. Hãy trả về tiền tố chung dài nhất. Nếu không có tiền tố chung, trả về "".

Ví dụ

Input:  strs = ["flower", "flow", "flight"]
Output: "fl"

Input:  strs = ["dog", "racecar", "car"]
Output: ""
Giải thích: không có ký tự nào chung ngay từ vị trí đầu.

Ràng buộc

• 1 <= len(strs) <= 200
• 0 <= len(strs[i]) <= 200
• strs[i] chỉ chứa chữ thường.

Clarifying questions

• Mảng có thể có chuỗi rỗng không? → Có. Khi đó kết quả luôn là "".
• Phân biệt hoa/thường? → Theo đề chỉ chữ thường.
• Tiền tố là theo ký tự hay theo từ? → Theo ký tự (character-level).

Hướng tiếp cận

Cách 1 - Vertical scan, O(S) với S là tổng độ dài. Duyệt từng vị trí cột i = 0, 1, 2, .... Tại mỗi i, kiểm tra ký tự strs[0][i] có khớp với strs[j][i] cho mọi j không. Nếu có chuỗi nào hết hoặc khác → trả về strs[0][:i].

Cách 2 - Horizontal scan. Lấy prefix = strs[0], sau đó với mỗi chuỗi tiếp theo, rút ngắn prefix cho đến khi nó là tiền tố của chuỗi đó.

Cách 3 - Sort + so sánh 2 đầu, O(n log n · L). Sort mảng theo thứ tự lexicographic. Tiền tố chung dài nhất chính là tiền tố chung của strs[0] và strs[-1]. Hay nhưng không tối ưu time.

Mình giới thiệu vertical scan vì nó là cách dễ nhất để diễn đạt trên whiteboard và có thể early-exit ngay khi gặp mismatch đầu tiên.

Code Python 3

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        for i, ch in enumerate(strs[0]):
            for s in strs[1:]:
                if i >= len(s) or s[i] != ch:
                    return strs[0][:i]
        return strs[0]  # toàn bộ strs[0] là tiền tố chung

Phân tích độ phức tạp

• Thời gian: O(S) với S = Σ len(strs[i]) (trong worst case).
• Bộ nhớ: O(1).

Bình luận

• Bẫy thường gặp:
  • Quên check i >= len(s) → IndexError khi có chuỗi ngắn hơn strs[0].
  • Trả về strs[0] khi đáng lẽ phải trả về tiền tố ngắn hơn.
• Follow-up phổ biến:
  1. “Nếu danh sách strs được thêm dần (streaming), làm sao update prefix?” → Mỗi lần thêm string mới, rút prefix theo cách horizontal.
  2. “Nếu dùng Trie thì sao?” → Trie giúp khi có nhiều query prefix khác nhau, xem Chương 23.
• Edge cases bắt buộc test:
  • strs = [""] → kết quả "".
  • strs = ["a"] → kết quả "a".
  • strs = ["abc", "abc"] → kết quả "abc".

Bài tự luyện liên quan

• LC 58 - Length of Last Word.
• LC 1408 - String Matching in an Array.
• LC 720 - Longest Word in Dictionary (dùng Trie, Chương 23).

---

2.4 String to Integer / atoi (LC 8)

Đề bài

Cài đặt hàm atoi (ASCII to Integer) chuyển một chuỗi thành số nguyên 32-bit có dấu. Quy tắc:

1. Bỏ qua khoảng trắng đầu chuỗi.
2. Đọc dấu + hoặc - (tuỳ chọn).
3. Đọc các ký tự số liên tiếp cho đến khi gặp ký tự không phải số.
4. Áp dấu vào kết quả.
5. Clamp vào phạm vi int 32-bit: [-2^31, 2^31 - 1].
6. Trả về 0 nếu không đọc được số nào (ví dụ chuỗi toàn chữ).

Ví dụ

Input:  s = "42"
Output: 42

Input:  s = "   -42"
Output: -42                (bỏ space đầu, đọc dấu '-', rồi đọc "42")

Input:  s = "4193 with words"
Output: 4193               (dừng tại khoảng trắng sau "4193"; phần "with words" bị bỏ)

Input:  s = "words and 987"
Output: 0                  (gặp 'w' đầu tiên ngay sau khi bỏ space → không đọc được số nào)

Input:  s = "-91283472332"
Output: -2147483648        (= INT_MIN, clamp vì -91283472332 < -2^31)

Input:  s = "+-12"
Output: 0                  (đã đọc dấu '+', sau đó gặp '-' không phải digit → fail ngay)

Ràng buộc

• 0 <= len(s) <= 200
• s chứa chữ in hoa, in thường, số, ’ ‘,’+‘,’-‘,’.’.

Clarifying questions

• Số “0042” có hợp lệ không? → Có, kết quả = 42.
• Có hỗ trợ số thập phân, hex, scientific không? → Không, chỉ integer thập phân.
• Overflow xử lý sao? → Clamp về INT_MIN / INT_MAX. Không raise exception.

Hướng tiếp cận

Cách 1 - Quy trình tuần tự, dùng index chạy qua chuỗi. 4 bước rõ ràng: skip space → đọc dấu → đọc số → clamp. Mỗi bước có biến trạng thái riêng.

Cách 2 - Finite State Machine (FSM). Mô hình trạng thái giúp code gọn hơn và dễ mở rộng khi đề bài thêm yêu cầu (số thực, scientific notation, …). Rất đáng học vì đây là pattern chung cho mọi bài parser (Chương 32).

Hình minh hoạ FSM:

       blank        sign        digit       khác
   ┌───────────────────────────────────────────────┐
S  │  start  →  start    signed   in_number   end │
T  │  signed →  end      end      in_number   end │
A  │ in_num  →  end      end      in_number   end │
T  │  end    →  end      end      end         end │
E  └───────────────────────────────────────────────┘

Trạng thái:
  start     : đang skip space đầu
  signed    : đã đọc 1 dấu, chờ digit
  in_number : đang đọc các chữ số
  end       : đã kết thúc, mọi ký tự sau bị ignore

Code Python 3

INT_MAX = 2**31 - 1   # 2147483647
INT_MIN = -2**31      # -2147483648

class Solution:
    """Cách 1 - quy trình tuần tự."""

    def myAtoi(self, s: str) -> int:
        i, n = 0, len(s)

        # 1. Bỏ space đầu.
        while i < n and s[i] == ' ':
            i += 1

        # 2. Đọc dấu (tuỳ chọn).
        sign = 1
        if i < n and s[i] in '+-':
            sign = -1 if s[i] == '-' else 1
            i += 1

        # 3. Đọc các chữ số.
        result = 0
        while i < n and s[i].isdigit():
            result = result * 10 + (ord(s[i]) - ord('0'))
            # Tối ưu: có thể early-clamp ngay đây để khỏi overflow.
            if result > 2**31:   # vượt rất nhiều
                break
            i += 1

        # 4. Áp dấu và clamp.
        result *= sign
        return max(INT_MIN, min(INT_MAX, result))


class SolutionFSM:
    """Cách 2 - Finite State Machine. Dễ extend khi đề thêm yêu cầu."""

    table = {
        'start':     {'blank': 'start',  'sign': 'signed',   'digit': 'in_num', 'other': 'end'},
        'signed':    {'blank': 'end',    'sign': 'end',      'digit': 'in_num', 'other': 'end'},
        'in_num':    {'blank': 'end',    'sign': 'end',      'digit': 'in_num', 'other': 'end'},
        'end':       {'blank': 'end',    'sign': 'end',      'digit': 'end',    'other': 'end'},
    }

    @staticmethod
    def _kind(ch: str) -> str:
        if ch == ' ':           return 'blank'
        if ch in '+-':          return 'sign'
        if ch.isdigit():        return 'digit'
        return 'other'

    def myAtoi(self, s: str) -> int:
        state = 'start'
        sign = 1
        result = 0
        for ch in s:
            state = self.table[state][self._kind(ch)]
            if state == 'in_num':
                result = result * 10 + int(ch)
                result = min(result, INT_MAX + 1)  # chặn overflow sớm
            elif state == 'signed':
                sign = -1 if ch == '-' else 1
            elif state == 'end':
                break
        return max(INT_MIN, min(INT_MAX, sign * result))

Phân tích độ phức tạp

• Thời gian: O(n) - duyệt chuỗi đúng 1 lần.
• Bộ nhớ: O(1).

Bình luận

• Bẫy thường gặp:
  • Quên clamp → bị overflow ở các ngôn ngữ có int 32-bit. Python int vô hạn nên không TLE, nhưng vẫn phải clamp theo đề.
  • Đọc dấu sai: không cho phép +-12 hay ++12 → phải end ngay khi gặp dấu thứ 2.
  • Skip space chỉ ở đầu, không phải mọi space. " 1 2 3" → kết quả là 1.
  • Trim chuỗi trước bằng s.strip() là sai - nó loại bỏ cả space cuối, không phải vấn đề; nhưng cẩn thận s.lstrip() thay vì strip().
• Follow-up phổ biến:
  1. LC 65 - Valid Number: phức tạp hơn với ., e, dấu, … → bắt buộc dùng FSM (Chương 32).
  2. Xử lý số nhị phân, hex (prefix 0b, 0x).
  3. Số dấu phẩy động.
• Tại sao đáng đầu tư FSM? Đây là pattern bạn sẽ gặp lại ở:
  • Valid Number (LC 65), Number of Atoms (LC 726), Tag Validator (LC 591) - toàn bộ Chương 32 đều xây trên ý tưởng FSM.

Bài tự luyện liên quan

• LC 65 - Valid Number.
• LC 12 - Integer to Roman / LC 13 - Roman to Integer.
• LC 415 - Add Strings.

---

2.5 Group Anagrams (LC 49)

Đề bài

Cho mảng chuỗi strs. Hãy gom các chuỗi là anagram của nhau vào cùng một nhóm. Trả về danh sách các nhóm (thứ tự nhóm và thứ tự trong nhóm không quan trọng).

Ví dụ

Input:  strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Ràng buộc

• 1 <= len(strs) <= 10^4
• 0 <= len(strs[i]) <= 100
• strs[i] chỉ chứa chữ thường.

Clarifying questions

• Output có cần sort không? → Không, miễn là gom đúng nhóm.
• Chuỗi rỗng được xử lý sao? → Tất cả chuỗi rỗng vào cùng 1 nhóm (anagram của nhau).
• Phân biệt hoa/thường? → Theo đề chỉ chữ thường.

Hướng tiếp cận

Ý tưởng cốt lõi: Hai chuỗi là anagram ↔︎ có cùng “chữ ký”. Ta dùng dict {chữ_ký: list các chuỗi} để gom.

Cách 1 - Chữ ký = sorted(s), O(n · k log k). key = ''.join(sorted(s)). Hai anagram sẽ có cùng sorted form.

Cách 2 - Chữ ký = tuple count 26 chữ, O(n · k). key = tuple(Counter(s)[ch] for ch in 'abcdefghijklmnopqrstuvwxyz'). Tránh được phép sort O(k log k) nhưng tuple 26 phần tử có overhead.

Hình minh hoạ với ["eat", "tea", "tan", "ate", "nat", "bat"]:

str    sorted_key   bucket
─────  ───────────  ─────────────────────
"eat"   "aet"  ──┐
"tea"   "aet"  ──┤───►  bucket "aet" = ["eat", "tea", "ate"]
"ate"   "aet"  ──┘
"tan"   "ant"  ──┐
"nat"   "ant"  ──┤───►  bucket "ant" = ["tan", "nat"]
"bat"   "abt"  ──────►  bucket "abt" = ["bat"]

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups: dict[str, list[str]] = defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            groups[key].append(s)
        return list(groups.values())


class SolutionCount:
    """Chữ ký = tuple count 26 chữ - không cần sort."""

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups: dict[tuple, list[str]] = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for ch in s:
                count[ord(ch) - ord('a')] += 1
            groups[tuple(count)].append(s)
        return list(groups.values())

Phân tích độ phức tạp

Cách	Time	Space
sorted-key	O(n · k log k)	O(n·k)
count-key	O(n · k)	O(n·k)

Với n = số chuỗi, k = độ dài chuỗi.

Bình luận

• Khi nào dùng cách nào?
  • k rất nhỏ (≤ 100, như LC) → cả 2 đều ổn, sorted-key gọn hơn.
  • k lớn (≥ 10^4) → count-key thắng vì O(k) < O(k log k).
  • Bảng chữ rất lớn (Unicode) → cũng phải dùng Counter, tránh tuple 1000+ phần tử.
• Bẫy thường gặp: Quên ''.join sau sorted() - sẽ ra list không hash được.
• Follow-up phổ biến:
  1. LC 438 - Find All Anagrams in a String: sliding window (Chương 27).
  2. Streaming: thêm chuỗi 1 cái → update group nhanh? → dùng dict in-place.

Bài tự luyện liên quan

• LC 242 - Valid Anagram (bài 2.1).
• LC 438 - Find All Anagrams in a String.
• LC 1207 - Unique Number of Occurrences.

---

2.6 Reverse Words in a String (LC 151)

Đề bài

Cho chuỗi s chứa nhiều từ cách nhau bởi ít nhất 1 dấu cách. Hãy đảo thứ tự các từ và trả về chuỗi kết quả, sao cho:

• Chỉ có 1 dấu cách giữa các từ trong kết quả.
• Không có dấu cách ở đầu hoặc cuối.

Ví dụ

Input:  s = "the sky is blue"
Output: "blue is sky the"

Input:  s = "  hello world  "
Output: "hello world"   (gọn space đầu/cuối + giữa)

Input:  s = "a good   example"
Output: "example good a"   (gộp nhiều space giữa thành 1)

Ràng buộc

• 1 <= len(s) <= 10^4
• s chứa chữ in hoa, in thường, số, và dấu cách ' '.
• s chứa ít nhất một từ.
• Follow-up: làm in-place với O(1) extra space (chỉ áp dụng nếu input là mảng ký tự có thể sửa được - như C/C++).

Clarifying questions

• “Từ” là gì? → Một dãy ký tự không phải space liên tiếp.
• Có dấu câu, dấu cách đặc biệt không? → Theo LC chỉ là ASCII space.
• Có thể dùng s.split() không? → Có, đây là cách Pythonic. Nhưng follow-up trên mảng ký tự sẽ yêu cầu 3-reverse trick.

Hướng tiếp cận

Cách 1 - Pythonic split-reverse-join, O(n). return ' '.join(reversed(s.split())). split() không tham số sẽ tự gộp nhiều space và bỏ space đầu/cuối - chính xác cái ta cần.

Cách 2 - Three Reverses (in-place trên mảng ký tự). Áp dụng đúng ý tưởng của bài Rotate Array (1.6): 1. Reverse toàn bộ chuỗi. 2. Reverse từng “từ” trong chuỗi đã reverse. 3. Dọn space (chỉ giữ 1 space giữa từ, bỏ space đầu/cuối).

Hình minh hoạ với s = "the sky is blue":

Input               :  "the sky is blue"

Bước 1: reverse toàn bộ
                       "eulb si yks eht"

Bước 2: reverse từng từ trong chuỗi đã đảo
                       "blue is sky the"   ← đáp án ✓

So sánh với Rotate Array: Rotate Array reverse trên đơn vị phần tử, Reverse Words reverse trên đơn vị “từ” (substring giữa các space). Same idea, khác mức trừu tượng.

Code Python 3

class Solution:
    """Cách 1 - Pythonic, ngắn gọn nhất."""

    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))


class SolutionInPlace:
    """Cách 2 - Three reverses, in-place trên list ký tự."""

    def reverseWords(self, s: str) -> str:
        chars = list(s.strip())  # Python string immutable → phải chuyển list

        # 1. Reverse toàn bộ.
        self._reverse(chars, 0, len(chars) - 1)

        # 2. Reverse từng từ.
        start = 0
        for i in range(len(chars) + 1):
            if i == len(chars) or chars[i] == ' ':
                self._reverse(chars, start, i - 1)
                start = i + 1

        # 3. Gộp nhiều space giữa các từ thành 1.
        return self._collapse_spaces(chars)

    @staticmethod
    def _reverse(arr: list, l: int, r: int) -> None:
        while l < r:
            arr[l], arr[r] = arr[r], arr[l]
            l += 1
            r -= 1

    @staticmethod
    def _collapse_spaces(chars: list) -> str:
        out, prev_space = [], False
        for ch in chars:
            if ch == ' ':
                if not prev_space and out:
                    out.append(' ')
                prev_space = True
            else:
                out.append(ch)
                prev_space = False
        if out and out[-1] == ' ':
            out.pop()
        return ''.join(out)

Phân tích độ phức tạp

• Cách 1: O(n) time, O(n) space (Python tạo chuỗi mới).
• Cách 2: O(n) time, O(n) space cho chars (Python immutable string). Nếu input là list[str] (như C/C++ char array), thì là O(1) extra space.

Bình luận

• Bẫy thường gặp:
  • Quên xử lý nhiều space giữa các từ → kết quả còn dư space.
  • Quên .strip() → space đầu/cuối còn nguyên.
  • Reverse từng từ nhưng để start = i thay vì i + 1 → ký tự bị tính 2 lần.
• Follow-up phổ biến:
  1. LC 557 - Reverse Words in a String III: chỉ reverse trong từng từ, không đảo thứ tự từ.
  2. LC 186 - Reverse Words in a String II: input là char[], làm in-place O(1) space - đúng bài cách 2 áp dụng.
  3. “Nếu chuỗi rất lớn, không fit RAM?” → Stream từ cuối lên đầu, gom từng từ.
• Liên hệ với Rotate Array (Chương 1): Same 3-reverse pattern, khác đơn vị. Khi gặp bài “đảo theo block” hãy nghĩ ngay đến 3-reverse.

Bài tự luyện liên quan

• LC 557 - Reverse Words in a String III.
• LC 186 - Reverse Words in a String II (in-place).
• LC 344 - Reverse String.

Tóm tắt chương & Quyết định

Giả thiết về ký tự - làm rõ ngay trước khi viết code

1. Bảng chữ cái: lowercase a–z (26)? ASCII 128? Unicode? - Mảng đếm [26] chỉ dùng được khi đúng 26 chữ.
2. Phân biệt hoa thường? - "Aa" có là palindrome không? LC 125 lowercase trước; LC 5 không.
3. Có ký tự không phải chữ-và-số? - Lọc bằng isalnum(), hay đề bài đã đảm bảo sạch?
4. Có khoảng trắng đầu/cuối? - Gọi strip() trước khi parse số.

String pattern map

Pattern	Khi gặp	Chương
Counting (Counter, [26])	Anagram, frequency	02, 06
Two pointers (in/out)	Palindrome, reverse	02, 26
Sliding window	Substring với ràng buộc động	27
Parsing với stack/FSM	atoi, calculator, Decode	08, 32
Pattern matching	strStr, anagrams trong text	35, 36, 34
Hashing string	Rabin-Karp, Distinct substrings	34

Group Anagrams - chọn key thế nào?

• Sorted string key "eat" → "aet": code 2 dòng, O(n·k log k).
• Tuple 26 count (0,0,1,...,1,...): O(n·k), nhanh hơn khi k lớn và bảng chữ cái nhỏ.
• Trong phỏng vấn: nói cả 2 cách, viết sorted (đẹp); đánh đổi sang dạng đếm tuple khi cần tối ưu.

Bridge sang Chương 32 (String Parser)

LC 8 (atoi) là FSM nhỏ (4 trạng thái: start, sign, digits, overflow). Khi đề bài phức tạp hơn (Valid Number, Calculator) → đọc Chương 32.

---