Giải quyết tập dữ liệu nhỏ

Cách đơn giản nhất là thử mọi chuỗi con có thể có của tên đã cho. Đối với một chuỗi con cụ thể, chúng ta chỉ cần kiểm tra xem có tồn tại ít nhất \(n\) phụ âm liên tiếp hay không. Nếu đúng, chúng ta cộng chuỗi con này vào giá trị \(n\). Có \(O(L^2)\) chuỗi con, và mất \(O(L)\) thời gian để kiểm tra điều kiện ít nhất \(n\) phụ âm liên tiếp. Tổng cộng mỗi bộ test mất \(O(L^3)\) thời gian để giải quyết, điều này có thể chấp nhận được đối với dữ liệu nhỏ. Tuy nhiên, cách tiếp cận này không đủ nhanh để giải quyết dữ liệu lớn.

Cải tiến thuật toán ngây thơ

Thực tế, chúng ta có thể bỏ qua việc kiểm tra tuyến tính cho tất cả các chuỗi con. Giả sử chúng ta bắt đầu từ ký tự thứ \(i\) (chỉ số bắt đầu từ 0). Chúng ta cũng có biến \(c\) bắt đầu bằng 0. Khi duyệt đến ký tự thứ \(j\), nếu đó là phụ âm, ta tăng \(c\) thêm 1, ngược lại đặt \(c\) về 0. Thực chất \(c\) là số lượng phụ âm liên tiếp kết thúc tại ký tự thứ \(j\). Nếu ta gặp trường hợp đầu tiên mà \(c \ge n\), ta có thể kết luận rằng mọi chuỗi con bắt đầu tại ký tự thứ \(i\) và kết thúc tại ký tự thứ \(k\), với \(k \ge j\), đều là chuỗi con thỏa mãn. Khi đó, ta có thể cộng \(L - j\) vào kết quả và chuyển sang ký tự bắt đầu tiếp theo. Thuật toán này chạy trong \(O(L^2)\), vẫn chưa đủ tốt cho dữ liệu lớn. Nhưng khái niệm tính toán \(c\) chính là chìa khóa để giải quyết hoàn toàn bài toán.

Cải tiến thêm

Hãy mở rộng định nghĩa của \(c\) cho mọi ký tự, gọi là \(c_i\): số lượng phụ âm liên tiếp kết thúc tại ký tự thứ \(i\). Ví dụ, giả sử chuỗi là quartz, thì \(c_0 = 1, c_2 = 0, c_5 = 3\). Chúng ta có thể tính toán mọi \(c_i\) trong \(O(L)\) thời gian. Đồng thời định nghĩa cặp \((x, y)\) là chuỗi con bắt đầu tại ký tự thứ \(x\) và kết thúc tại ký tự thứ \(y\).

Từ phần trước, nếu ta biết \(c_i \ge n\), thì các chuỗi con \((i - n - r + 2, i + q)\) sẽ được tính. Tuy nhiên, để tránh đếm lặp, chúng ta cần xác định phạm vi bắt đầu hợp lý. Cụ thể, ta cần lưu lại vị trí cuối cùng \(j < i\) sao cho \(c_j \ge n\). Gọi \(r\) là vị trí bắt đầu của cụm \(n\) phụ âm liên tiếp gần nhất được tìm thấy trước đó. Nếu tìm thấy một cụm \(n\) phụ âm liên tiếp kết thúc tại \(i\), thì tất cả các chuỗi con bắt đầu từ bất kỳ vị trí nào từ \(r\) (vị trí bắt đầu của cụm thỏa mãn trước đó) lùi về đầu chuỗi, và kết thúc tại \(i\) hoặc sau \(i\), đều đã được tính hoặc cần được tính cẩn thận.

Cách tiếp cận chính xác hơn: Duyệt qua chuỗi, duy trì số lượng phụ âm liên tiếp hiện tại. Khi tìm thấy một vị trí \(i\) mà tại đó có ít nhất \(n\) phụ âm liên tiếp (tức là đoạn từ \(i-n+1\) đến \(i\) toàn là phụ âm), thì bất kỳ chuỗi con nào bắt đầu từ vị trí \(p\) (\(0 \le p \le i-n+1\)) và kết thúc tại \(q\) (\(i \le q < L\)) đều chứa cụm phụ âm này. Để tránh đếm trùng, với mỗi vị trí \(i\) kết thúc một cụm \(n\) phụ âm, ta chỉ đếm các chuỗi con bắt đầu từ vị trí sau vị trí bắt đầu của cụm thỏa mãn gần nhất trước đó.

Cụ thể, gọi last_pos là chỉ số bắt đầu của cụm \(n\) phụ âm liên tiếp gần nhất được tìm thấy. Khi tại vị trí \(i\) ta tìm thấy một cụm mới (tức là \(c_i \ge n\)), số lượng chuỗi con mới được thêm vào là: (vị trí bắt đầu cụm hiện tại - last_pos + 1) * (số lượng vị trí kết thúc còn lại).
Trong đó:

• Vị trí bắt đầu cụm hiện tại là \(i - n + 1\).
• Số lượng vị trí kết thúc còn lại là \(L - i\).
• last_pos ban đầu bằng 0. Sau mỗi lần tìm thấy cụm thỏa mãn, last_pos được cập nhật thành \((i - n + 2)\).

Tổng thời gian chạy là \(O(L)\), đủ để vượt qua tập dữ liệu lớn.

Cách cài đặt

Mặc dù có vẻ phức tạp, thuật toán lại cực kỳ đơn giản. Dưới đây là mã nguồn tham khảo:

def Solve(s, n):
  L = len(s)
  cnt, r, c = 0, 0, 0
  for i in range(L):
    c = c + 1 if s[i] not in "aeiou" else 0
    if c >= n:
      cnt += (i - n - r + 2) * (L - i)
      r = i - n + 2
  return cnt

Dựa trên phân tích chính thức của Google Code Jam.