Maximize the Confusion of an Exam (LeetCode 2024)

Nguồn: LeetCode 2024 Độ khó: Trung bình Hai con trỏ Cửa sổ trượt Xâu

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

LeetCode 2024 – Maximize the Confusion of an Exam (Làm rối đề thi nhiều nhất) – độ khó Medium.

Một thầy giáo đang soạn một bài kiểm tra gồm $n$ câu hỏi đúng/sai, trong đó 'T' nghĩa là đúng (true) và 'F' nghĩa là sai (false). Thầy muốn làm học sinh bối rối bằng cách làm cho số câu hỏi liên tiếp có cùng đáp án (nhiều câu đúng liên tiếp hoặc nhiều câu sai liên tiếp) là lớn nhất.

Cho xâu answerKey, trong đó answerKey[i] là đáp án ban đầu của câu hỏi thứ $i$. Ngoài ra cho số nguyên $k$ – số lần tối đa được thực hiện thao tác sau:

• Đổi đáp án của một câu hỏi bất kỳ thành 'T' hoặc 'F' (tức là gán answerKey[i] bằng 'T' hoặc 'F').

Yêu cầu: trả về số lượng lớn nhất các ký tự 'T' liên tiếp hoặc các ký tự 'F' liên tiếp trong xâu đáp án sau khi thực hiện thao tác không quá $k$ lần.

Ràng buộc:

• n == answerKey.length
• $1 \le n \le 5 \cdot 10^4$
• answerKey[i] là 'T' hoặc 'F'
• $1 \le k \le n$

Ví dụ 1:

Input: answerKey = "TTFF", k = 2
Output: 4

Giải thích: ta đổi cả hai chữ 'F' thành 'T' để được "TTTT". Có 4 chữ 'T' liên tiếp.

Ví dụ 2:

Input: answerKey = "TFFT", k = 1
Output: 3

Giải thích: đổi chữ 'T' đầu tiên thành 'F' để được "FFFT", hoặc đổi chữ 'T' thứ hai thành 'F' để được "TFFF". Trong cả hai trường hợp đều có 3 chữ 'F' liên tiếp.

Ví dụ 3:

Input: answerKey = "TTFTTFTT", k = 1
Output: 5

Giải thích: đổi chữ 'F' thứ nhất để được "TTTTTFTT", hoặc đổi chữ 'F' thứ hai để được "TTFTTTTT". Trong cả hai trường hợp đều có 5 chữ 'T' liên tiếp.

2024. Maximize the Confusion of an Exam – Medium.

A teacher is writing a test with $n$ true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

You are given a string answerKey, where answerKey[i] is the original answer to the $i^{th}$ question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:

• Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').

Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.

Example 1:

Input: answerKey = "TTFF", k = 2
Output: 4
Explanation: We can replace both the 'F's with 'T's to make answerKey = "TTTT".
There are four consecutive 'T's.

Example 2:

Input: answerKey = "TFFT", k = 1
Output: 3
Explanation: We can replace the first 'T' with an 'F' to make answerKey = "FFFT".
Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".
In both cases, there are three consecutive 'F's.

Example 3:

Input: answerKey = "TTFTTFTT", k = 1
Output: 5
Explanation: We can replace the first 'F' to make answerKey = "TTTTTFTT"
Alternatively, we can replace the second 'F' to make answerKey = "TTFTTTTT".
In both cases, there are five consecutive 'T's.

Constraints:

• n == answerKey.length
• 1 <= n <= 5 * 10^4
• answerKey[i] is either 'T' or 'F'
• 1 <= k <= n

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Về dữ liệu vào / ra của code trong bài

Trên LeetCode các bạn chỉ cần nộp phần class Solution. Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng 1 là xâu answerKey (chỉ gồm chữ T, F, không có dấu nháy), dòng 2 là số $k$; in ra một số nguyên là đáp án. Ví dụ 3 sẽ nhập là:

TTFTTFTT
1

và chương trình in ra 5.

Tóm tắt đề bài: ta có một xâu $a$ gồm các chữ cái 'T' hoặc 'F' và số nguyên dương $k$. Ta được biến đổi không quá $k$ ký tự, từ 'T' thành 'F' hoặc từ 'F' thành 'T', sao cho số lượng ký tự giống nhau liên tiếp là nhiều nhất có thể.

Ví dụ 3: TTFTTFTT với $k = 1$. Nếu đổi chữ F ở vị trí 2 (đếm từ 0) thành T thì đoạn từ vị trí 0 đến 4 thành TTTTT – 5 chữ T liên tiếp. Không thể được 6: mọi đoạn dài 6 đều chứa đủ 2 chữ F mà ta chỉ được đổi 1 chữ. Nên đáp án là 5.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Thử mọi đoạn · O(n²) · TLECách 2Hai con trỏ (cách của mình) · O(n)

Cách 1Thử mọi đoạn [l..r] – O(n²)

Trước khi vào cách chính, mình nói qua cách "ngây thơ" để các bạn thấy vì sao cần hai con trỏ.

Một đoạn $[l..r]$ có thể biến thành toàn ký tự giống nhau khi nào? Muốn cả đoạn là T thì phải đổi hết các chữ F trong đoạn; muốn cả đoạn là F thì phải đổi hết các chữ T. Tất nhiên ta chọn phương án tốn ít lần đổi hơn:

Điều kiện một đoạn dùng được

Đoạn $[l..r]$ biến được thành toàn ký tự giống nhau $\iff \min(cntT, cntF) \le k$, với $cntT$, $cntF$ là số chữ T, F trong đoạn.

Vậy chỉ cần cố định $l$, cho $r$ chạy từ $l$ tới $n - 1$, vừa chạy vừa cộng dồn $cntT$, $cntF$, thấy đoạn thỏa điều kiện thì cập nhật đáp án bằng độ dài $r - l + 1$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxConsecutiveAnswers(string a, int k) {
        int n = (int) a.size();
        int ans = 0;
        for (int l = 0; l < n; l++) {
            int cntT = 0, cntF = 0;
            for (int r = l; r < n; r++) {
                if (a[r] == 'T') cntT++;
                else cntF++;
                // muốn cả đoạn giống nhau thì đổi nhóm ít hơn
                if (min(cntT, cntF) <= k) {
                    ans = max(ans, r - l + 1);
                }
            }
        }
        return ans;
    }
};

int main() {
    string a;
    int k;
    cin >> a >> k;
    Solution sol;
    cout << sol.maxConsecutiveAnswers(a, k);
    return 0;
}

class Solution:
    def maxConsecutiveAnswers(self, a: str, k: int) -> int:
        n = len(a)
        ans = 0
        for l in range(n):
            cntT = cntF = 0
            for r in range(l, n):
                if a[r] == 'T':
                    cntT += 1
                else:
                    cntF += 1
                # muốn cả đoạn giống nhau thì đổi nhóm ít hơn
                if min(cntT, cntF) <= k:
                    ans = max(ans, r - l + 1)
        return ans

def main():
    data = input().split()
    a = data[0]
    k = int(data[1]) if len(data) > 1 else int(input())
    print(Solution().maxConsecutiveAnswers(a, k))

main()

Không gian$O(1)$

Thời gian$O(n^2)$

Bị TLE

Với $n = 5 \cdot 10^4$ thì số đoạn là khoảng $1.25 \cdot 10^9$ – quá nhiều. Cách này chỉ dùng để hiểu bài và làm code vét cạn đối chiếu thôi nha các bạn.

Cách 2Hai con trỏ, xét riêng T và F – O(n)

Phương pháp giải: Two pointers (hai con trỏ).

Vì ta chỉ cần số lượng ký tự giống nhau, cho nên ta có thể xét riêng những dãy giống nhau là 'T' và những dãy giống nhau là 'F', rồi lấy kết quả lớn hơn.

Để xét dãy giống nhau gồm các ký tự 'T' liên tiếp, ta thấy rằng đoạn $[l..r]$ sẽ có thể biến thành toàn bộ chữ 'T' nếu ở giữa đoạn $[l..r]$ có không quá $k$ chữ 'F'.

Ta gọi $cntF$ là số lượng chữ 'F' trong đoạn đang xét, đặt $l = 0$. Với mỗi giá trị $i$ (đầu phải của đoạn):

• Nếu $a[i] = $ 'F', ta tăng $cntF$ lên 1 đơn vị.
• Nếu hiện tại $cntF \gt k$, ta tiến hành dịch $l$ lên: nếu $a[l] = $ 'F' thì ta giảm $cntF$ đi 1. Dịch $l$ lên cho đến khi $cntF \le k$.
• Như vậy đoạn $[l..i]$ là một đoạn hoàn toàn có thể biến đổi thành 'T'. Ta cập nhật $ans = \max(ans, i - l + 1)$.

Làm điều tương tự khi xét dãy giống nhau gồm các ký tự 'F' liên tiếp (lúc này đếm $cntT$).

Vì sao $l$ chỉ cần đi tới, không bao giờ lùi?

Nếu đoạn $[l..i]$ đã có quá $k$ chữ F thì mọi đoạn $[l..j]$ với $j \gt i$ còn chứa nhiều chữ F hơn nữa ⇒ đầu trái $l$ đó vô dụng với mọi đầu phải sau này, bỏ hẳn được. Vì vậy $l$ chỉ tăng, tổng cộng tăng không quá $n$ lần, còn $i$ chạy đúng $n$ lần ⇒ mỗi lượt chỉ tốn $O(n)$. Đồng thời với mỗi $i$, $l$ là đầu trái nhỏ nhất hợp lệ nên $i - l + 1$ là đoạn dài nhất kết thúc tại $i$.

Minh hoạ cửa sổ trượt

Em nhập xâu và $k$ rồi bấm Tiếp. Ô xanh là ký tự đã đúng mục tiêu, ô vàng là ký tự trong cửa sổ cần đổi, ô đỏ là ký tự làm cửa sổ "quá tải" (vượt $k$ lần đổi), ô mờ là nằm ngoài cửa sổ:

answerKey k

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé (bản Python mình gộp 2 lượt vào một vòng for bad in ('F', 'T') cho gọn, logic y hệt):

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxConsecutiveAnswers(string a, int k) {
        int n = (int) a.size();
        int l = 0;
        int cntF = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 'F') {
                cntF++;
            }
            while (cntF > k) {
                if (a[l] == 'F') {
                    cntF--;
                }
                l++;
            }
            ans = max(ans, i - l + 1);
        }
        int cntT = 0;
        l = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 'T') {
                cntT++;
            }
            while (cntT > k) {
                if (a[l] == 'T') {
                    cntT--;
                }
                l++;
            }
            ans = max(ans, i - l + 1);
        }
        return ans;
    }
};

int main() {
    string a;
    int k;
    cin >> a >> k;
    Solution sol;
    cout << sol.maxConsecutiveAnswers(a, k);
    return 0;
}

class Solution:
    def maxConsecutiveAnswers(self, a: str, k: int) -> int:
        n = len(a)
        ans = 0
        # lần 1: biến đoạn [l..i] thành toàn 'T' (đếm số 'F'),
        # lần 2: biến đoạn [l..i] thành toàn 'F' (đếm số 'T')
        for bad in ('F', 'T'):
            l = 0
            cnt = 0
            for i in range(n):
                if a[i] == bad:
                    cnt += 1
                while cnt > k:
                    if a[l] == bad:
                        cnt -= 1
                    l += 1
                ans = max(ans, i - l + 1)
        return ans

def main():
    data = input().split()
    a = data[0]
    k = int(data[1]) if len(data) > 1 else int(input())
    print(Solution().maxConsecutiveAnswers(a, k))

main()

C++▶ Chạy tay từng dòng codeHai con trỏ: lượt 1 đếm F (biến thành T), lượt 2 đếm T (biến thành F).

Dữ liệu vào (stdin) – sửa thoải máiTTFTTFTT 1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4class Solution {

5public:

6 int maxConsecutiveAnswers(string a, int k) {

7 int n = (int) a.size();

8 int l = 0;

9 int cntF = 0;

10 int ans = 0;

11 for (int i = 0; i < n; i++) {

12 if (a[i] == 'F') {

13 cntF++;

14 }

15 while (cntF > k) {

16 if (a[l] == 'F') {

17 cntF--;

18 }

19 l++;

20 }

21 ans = max(ans, i - l + 1);

22 }

23 int cntT = 0;

24 l = 0;

25 for (int i = 0; i < n; i++) {

26 if (a[i] == 'T') {

27 cntT++;

28 }

29 while (cntT > k) {

30 if (a[l] == 'T') {

31 cntT--;

32 }

33 l++;

34 }

35 ans = max(ans, i - l + 1);

36 }

37 return ans;

38 }

39};

40

41int main() {

42 string a;

43 int k;

44 cin >> a >> k;

45 Solution sol;

46 cout << sol.maxConsecutiveAnswers(a, k);

47 return 0;

48}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Thời gian: mỗi lượt, $i$ chạy $n$ lần và $l$ cũng chỉ tăng tối đa $n$ lần (không bao giờ lùi) ⇒ $O(n)$ cho mỗi lượt, 2 lượt vẫn là $O(n)$.
• Không gian: chỉ dùng vài biến đếm ⇒ $O(1)$ (không tính xâu đầu vào).

Không gian$O(1)$

Thời gian$O(n)$

Mẹo nhận dạng

Dạng "đoạn con dài nhất thỏa điều kiện, mà nếu đoạn lớn đã hỏng thì kéo dài thêm càng hỏng" gần như luôn giải được bằng hai con trỏ / cửa sổ trượt. Bài LeetCode 1004 – Max Consecutive Ones III chính là một lượt của bài này đó các bạn.

Ghi chú của mình: code C++ và Python của cả 2 cách (đọc dữ liệu từ bàn phím như mô tả ở đầu bài) đã được kiểm tra với 3 ví dụ của đề và 400 bộ test ngẫu nhiên ($n \le 10$), so với code vét cạn thử mọi cách đổi – khớp hết. Với $n = 5 \cdot 10^4$: cách 2 chạy khoảng 0.03 giây (C++) và 0.2 giây (Python); cách 1 bản C++ chạy hơn 10 giây, bản Python hơn 100 giây ⇒ TLE đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇