Cho chuỗi nhị phân s, tách nó thành phần trái và phần phải (cả hai đều không rỗng). Điểm số bằng: số ký tự 0 ở phần trái cộng số ký tự 1 ở phần phải. Trả về điểm tối đa trên mọi cách tách hợp lệ.

Bài học kỹ thuật. Bài này tưởng cần quét lại từng điểm chia (O(n²)), nhưng điểm số có thể duy trì tăng dần trong một lần duyệt. Mẫu — tính tổng toàn cục, rồi di chuyển con trỏ đồng thời cập nhật hai bộ đếm — xuất hiện liên tục trong logic streaming và windowing.

Ý tưởng

Tưởng tượng điểm chia di chuyển từ trái sang phải, mỗi bước một ký tự. Hai thứ thay đổi ở mỗi bước:

  • Nếu ký tự mới ở bên trái là 0, điểm trái tăng 1.
  • Nếu là 1, nó rời khỏi bên phải, nên điểm phải giảm 1.

Nếu tính trước tổng số 1 toàn chuỗi, ta không bao giờ phải quét lại nửa bên phải. Điểm phải chỉ là "tổng số 1 trừ đi số 1 đã bị bên trái lấy".

Cách tiếp cận

  1. left = 0 — số 0 tích lũy bên trái.
  2. right = tổng số 1 trong chuỗi — điểm bên phải ban đầu.
  3. Duyệt đến ký tự áp chót:
    • 0 → left += 1
    • 1 → right -= 1
    • điểm = left + right; giữ giá trị lớn nhất.

Ta dừng ở length - 1 vì cả hai phần phải không rỗng.

function maxScore(s: string): number {
  let left = 0;
  let right = s.split("").reduce((sum, ch) => sum + parseInt(ch, 10), 0);
  let result = 0;
 
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === "0") {
      left += 1;
    } else {
      right -= 1;
    }
    result = Math.max(result, left + right);
  }
 
  return result;
}

Độ phức tạp

  • Thời gian: O(n) — một lần duyệt.
  • Bộ nhớ: O(1) — chỉ hai bộ đếm.

Bài học

Bất cứ khi nào một "điểm số" có thể biểu diễn bằng thứ đã tính cộng với thứ còn lại, hãy duy trì nó như một giá trị chạy thay vì tính lại. Một ý tưởng duy nhất đó là khoảng cách giữa brute force O(n²) và lời giải O(n).