Giả sử ta có một chuỗi text, ta được phép hoán đổi hai ký tự trong chuỗi. Ta phải tìm độ dài của chuỗi con (substring) dài nhất với các ký tự lặp lại. Ví dụ, nếu đầu vào là "ababa", kết quả sẽ là 3, vì nếu hoán đổi b đầu tiên với a cuối cùng, hoặc b cuối cùng với a đầu tiên, chuỗi ký tự lặp lại dài nhất là "aaa", độ dài 3.
Để giải quyết, ta thực hiện các bước sau:
Định nghĩa map cnt, đặt ret := 1, j := 0, n := kích thước text, v := 0, định nghĩa set x, và tạo map m lưu tần suất mỗi ký tự trong text.
Đặt a := '*' và b := '*'.
Với i từ 0 đến n-1:
Tăng cnt[text[i]] lên 1.
Chèn text[i] vào x.
Nếu cnt[text[i]] bằng 2, thì:
Nếu a là '*', đặt a := text[i], ngược lại b := text[i].
Nếu a không phải '*' và b cũng không phải '*' HOẶC kích thước x lớn hơn 2:
Giảm cnt[text[j]] xuống 1.
Nếu cnt[text[j]] bằng 1, thì:
Nếu text[j] là a, đặt a := '*', ngược lại b := '*'.
Nếu cnt[text[j]] bằng 0, xóa text[j] khỏi x.
greater := a nếu cnt[a] > cnt[b], ngược lại b.
Nếu kích thước x bằng 1 HOẶC m[greater] - cnt[greater] khác 0, thì:
ret := max(ret, i - j + 1).
Ngược lại ret := max(ret, i - j).
Trả về ret.
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ minh họa
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxRepOpt1(string text) { int ret = 1; map <char, int> cnt; int j = 0; int n = text.size(); int v = 0; set <char> x; map <char, int> m; for(int i = 0; i < text.size(); i++)m[text[i]]++; char a = '*', b ='*'; for(int i = 0; i < n; i++){ cnt[text[i]]++; x.insert(text[i]); if(cnt[text[i]] == 2){ if(a == '*'){ a = text[i]; }else{ b = text[i]; } } while(a != '*' && b != '*' || x.size() > 2){ cnt[text[j]]--; if(cnt[text[j]] == 1) { if(text[j] == a) { a ='*'; }else{ b = '*'; } } if(cnt[text[j]] == 0) x.erase(text[j]); j++; } char greater = cnt[a] > cnt[b] ? a : b; if(x.size() == 1 || m[greater] - cnt[greater]){ ret = max(ret, i - j + 1); }else{ ret = max(ret, i - j); } } return ret; } }; main(){ Solution ob; cout << (ob.maxRepOpt1("ababa")); }Đầu vào
"ababa"
Kết quả
3