Longest Repeating Character Replacement

+10

Bạn nhận được một chuỗi s gồm các chữ cái tiếng Anh viết hoa và một số nguyên k. Bạn có thể chọn tối đa k vị trí trong s và đổi chữ cái ở mỗi vị trí thành một chữ cái viết hoa khác bất kỳ.

Trả về độ dài của đoạn con dài nhất (substring), tức một dãy chữ cái liền kề, có cùng một chữ cái được lặp lại sau khi bạn thay đổi.

Hàm

characterReplacement(s: string, k: integer) → integer

sstring: chuỗi chữ cái viết hoa
kinteger: số chữ cái tối đa mà bạn có thể thay đổi
Trả vềinteger: độ dài của chuỗi con dài nhất gồm một chữ cái lặp lại mà bạn có thể tạo ra

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chỉ chứa các chữ cái tiếng Anh viết hoa.
0 ≤ k ≤ s.length

Ví dụ

Đầu vào: s = "BAAACAB"k = 1
Đầu ra: 5
Giải thích: Đổi C thành A sẽ khiến các chỉ số từ 1 đến 5 tạo thành AAAAA. Cả hai cửa sổ gồm sáu ký tự đều chứa một B và ký tự C, nên mỗi cửa sổ cần đổi hai ký tự.

Đầu vào: s = "AABBBAB"k = 2
Đầu ra: 6
Giải thích: Các chỉ số từ 1 đến 6 chứa ABBBAB, và đổi cả hai chữ A thành B sẽ tạo thành BBBBBB. Cả chuỗi chỉ có bốn chữ B trong tổng số bảy chữ, nên cần ba lần thay đổi.

Câu hỏi mở rộng

Điều gì thay đổi nếu s có thể chứa bất kỳ ký tự nào thay vì chỉ 26 chữ cái viết hoa?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Giữ lại chữ cái xuất hiện nhiều nhất trong một chuỗi con và thay đổi các chữ cái còn lại: với chuỗi con có độ dài len, nếu chữ cái xuất hiện nhiều nhất có mặt top lần thì cần thay đổi len - top chữ cái. Cửa sổ trượt tìm chuỗi con dài nhất thỏa mãn len - top ≤ k chỉ trong một lượt duyệt, vì cửa sổ không cần thu hẹp và top không bao giờ giảm.

Kiểm tra mọi chuỗi con

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Với mỗi vị trí bắt đầu, hãy tăng dần điểm kết thúc thêm một chữ cái, cập nhật số lần xuất hiện của từng chữ cái và top, rồi kiểm tra len - top ≤ k. Mỗi chuỗi con mới chỉ cần một lần cập nhật thay vì phải đếm lại từ đầu, và mọi chuỗi con đều được kiểm tra, nên bạn sẽ không bỏ lỡ chuỗi dài nhất có thể đạt được.

Chuỗi có độ dài n có khoảng n²/2 chuỗi con: 1.25 × 10^9 lần kiểm tra khi n = 5 × 10^4.

Thuật toán

Đặt best thành 0.
Với mỗi chỉ số bắt đầu, đặt lại 26 bộ đếm và top thành 0.
Di chuyển end từ vị trí bắt đầu đến chỉ số cuối cùng. Cộng s[end] vào bộ đếm tương ứng và tăng top nếu bộ đếm đó hiện có giá trị cao nhất.
Nếu end - start + 1 - top ≤ k, lưu độ dài nếu nó lớn hơn best.
Trả về best.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

Mỗi cửa sổ trượt ứng với một chữ cái mục tiêu

Ý tưởng

Trước tiên, hãy chọn chữ cái cuối cùng. Nếu cả đoạn cuối cùng đều là A, bạn cần tìm chuỗi con dài nhất có nhiều nhất k chữ cái không phải A.

Di chuyển right qua chuỗi và đếm số chữ cái không phải chữ cái mục tiêu trong cửa sổ. Khi số lượng vượt quá k, di chuyển left về phía trước cho đến khi số lượng trở lại k. Một cửa sổ đã vượt quá giới hạn sẽ vẫn vượt quá giới hạn khi dài thêm, vì vậy left không bao giờ lùi lại, và với mỗi right, cửa sổ là cửa sổ hợp lệ dài nhất kết thúc tại đó.

Chạy thuật toán với cả 26 chữ cái và giữ kết quả tốt nhất: 26 lượt duyệt tuyến tính qua tối đa 5 × 10^4 chữ cái. Độ phức tạp vẫn là O(n) chỉ vì bảng chữ cái có kích thước nhỏ.

Thuật toán

Với mỗi chữ cái mục tiêu từ A đến Z, bắt đầu một cửa sổ với left = 0 và others = 0.
Di chuyển right dọc theo chuỗi. Nếu s[right] không phải chữ cái mục tiêu, tăng others lên một.
Trong khi others > k, di chuyển left về phía trước, giảm others đi một nếu chữ cái rời khỏi cửa sổ không phải chữ cái mục tiêu.
Lưu right - left + 1 nếu giá trị này lớn hơn best.
Sau khi xét cả 26 chữ cái, trả về best.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

Một cửa sổ không bao giờ thu nhỏ

Ý tưởng

Duy trì 26 bộ đếm cho cửa sổ và top, tức số đếm cao nhất. Khi thêm s[right] khiến cửa sổ cần thay quá nhiều ký tự, hãy bỏ một chữ cái ở bên trái: cửa sổ trượt và giữ nguyên độ dài, vì chỉ cửa sổ dài hơn mới có thể phá kỷ lục. Nếu không, cửa sổ tăng thêm một ký tự. Độ dài cửa sổ luôn bằng kết quả tốt nhất từ trước đến nay, nên đáp án là n - left.

Khi một chữ cái rời khỏi cửa sổ, hãy giữ nguyên top, ngay cả khi lúc này nó cao hơn số đếm thực tế. Sau khi trượt, độ dài cửa sổ bằng chính xác top + k, nên để cửa sổ dài thêm thì một chữ cái phải xuất hiện top + 1 lần, và khi đó top cũng tăng theo. top cũ chỉ có thể khiến cửa sổ trượt, mà trượt thì không thể làm mất kỷ lục.

Với BAAACAB và k = 1, BAAAC cần thay 2 ký tự nên trượt thành AAAC. Chữ A tiếp theo làm top tăng lên 4 và cửa sổ dài thêm thành AAACA, có độ dài 5.

Thuật toán

Giữ 26 bộ đếm, left = 0 và top = 0.
Di chuyển right qua chuỗi: cộng s[right] vào bộ đếm tương ứng và tăng top nếu bộ đếm đó hiện lớn hơn.
Nếu right - left + 1 - top > k, xóa s[left] khỏi các bộ đếm và di chuyển left lên một bước. Không bao giờ giảm top.
Trả về độ dài cửa sổ cuối cùng, n - left.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

Lỗi thường gặp và trường hợp biên

Cộng k vào đoạn liên tiếp dài nhất. Với AAAB và k = 3, kết quả là 6, dài hơn cả chuỗi. Với BAAACAB và k = 1, kết quả là 4, nhưng đổi C sẽ nối hai đoạn thành một đoạn dài 5.
Đếm số lần thay đổi so với ký tự đầu tiên của cửa sổ thay vì ký tự xuất hiện nhiều nhất trong cửa sổ. BAAA chỉ cần thay đổi một lần, không phải ba lần.
Trả về n - left từ một vòng lặp thu hẹp cửa sổ bằng while và tính lại giá trị lớn nhất thực tế. Cửa sổ đó sẽ ngắn lại, vì vậy hãy lưu riêng best.
Tính độ dài cửa sổ bằng right - left. Cả hai đầu đều nằm trong cửa sổ, vì vậy hãy cộng thêm một.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán thay thế ký tự lặp lại dài nhất là bao nhiêu?

Giải pháp dùng một cửa sổ chạy trong thời gian O(n), trong đó n là độ dài của s: right duyệt qua mỗi chữ cái một lần và left di chuyển nhiều nhất một lần mỗi bước. Giải pháp dùng O(1) bộ nhớ bổ sung, gồm 26 biến đếm và một vài số nguyên.

Điều này khác gì so với bài toán chuỗi con dài nhất không có ký tự lặp lại?

Cả hai đều di chuyển qua chuỗi hai cạnh, nhưng quy tắc xác định cửa sổ hợp lệ lại khác nhau. Ở bài đó, không ký tự nào được phép lặp lại, nên cửa sổ thu hẹp cho đến khi không còn ký tự lặp. Ở đây, độ dài trừ đi số lần xuất hiện nhiều nhất phải không vượt quá k, nên cửa sổ có thể trượt với độ dài cố định.

Có thể giải bài toán này bằng tìm kiếm nhị phân không?

Đúng. Nếu có thể tạo được một chuỗi con có độ dài L thì mọi chuỗi con ngắn hơn nằm bên trong nó cũng tạo được, vì vậy bạn có thể tìm kiếm nhị phân theo L. Với mỗi L, trượt một cửa sổ có độ dài cố định đó và kiểm tra xem có vị trí nào cần nhiều nhất k lần thay đổi hay không. Cách này có độ phức tạp O(n log n), chậm hơn giải pháp dùng một cửa sổ.

def characterReplacement(s, k):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "BAAACAB"
k = 1

Đầu ra mong đợi

Longest Repeating Character Replacement

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Kiểm tra mọi chuỗi con

Mỗi cửa sổ trượt ứng với một chữ cái mục tiêu

Một cửa sổ không bao giờ thu nhỏ

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự