Đổi k kí tự để được xâu con liên tục cùng kí tự dài nhất

2017-07-21
Bài gốc

Codeforces 676C

Đề bài

Cho xâu s độ dài n chỉ chứa kí tự ‘a’ và ‘b’.

Tìm độ dài của xâu con liên tiếp cùng kí tự dài nhất khi thay đổi không quá k kí tự trên xâu s.

Giới hạn:

  • 1 ≤ n ≤ 1000 000; 0 ≤ k ≤ n
Định dạng test

Input:

  • Dòng đầu là n và k.
  • Dòng thứ hai là xâu s.

Output:

  • Độ dài dài nhất theo yêu cầu bài toán.

Ví dụ:

input:
4 2
abba
output:
4
Thuật toán

Two pointers:

Giả sử đang thực hiện tối đa k thay đổi kí tự ‘a’ thành ‘b’, dễ thấy cần thay đổi tối đa k vị trí của kí tự ‘a’ “liên tiếp” nhau (không tính các kí tự ‘b’ chen giữa).

Ví dụ: s = abababa. Với k = 2, có thể thay đổi các cặp hai vị trí ‘a’ liên tiếp nhau như sau:

bbbbaba -> độ dài cần tìm = 4.

abbbbba -> độ dài cần tìm = 5.

ababbbb -> độ dài cần tìm = 4.

Làm tương tự khi thay đổi từ ‘b’ sang ‘a’, cập nhập đáp án tại mỗi thay đổi.

Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

int n, k, res = 0;
string s;

void change_to(char to) {

    int changes = 0;
    int cur_len = 0;
    int j = 0;
    REP(i,n) {
        if (s[i] == to) {
            cur_len++;
        } else {
            if (changes < k) {
                changes++;
                cur_len++;
            } else {
                while(s[j] == to) {
                    j++;
                    cur_len--;
                }
                j++;
            }
        }
        res = max(res, cur_len);
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    cin >> s;

    change_to('a');
    change_to('b');
    cout << res;

    return 0;
}
Độ phức tạp

O(N)