Xâu Duy Nhất (Xauduynhat)
Đề bài
Xauduynhat – Xâu duy nhất
Cho một xâu kí tự chỉ gồm các kí tự chữ cái. Do yêu thích tính đơn nhất nên Nam muốn tìm ra một xâu con gồm các kí tự liên tiếp sao cho trong xâu này mỗi kí tự chỉ xuất hiện đúng 1 lần duy nhất.
Bạn được Nam nhờ giúp đỡ, hãy tìm giúp Nam xâu đạt yêu cầu có độ dài lớn nhất sẽ là bao nhiêu.
Input:
- Gồm một dòng duy nhất là xâu ban đầu $S$ (độ dài $\le 5 \cdot 10^4$).
Output:
- Gồm một số duy nhất là đáp án tìm được.
Giới hạn thời gian: 1.0 giây. Giới hạn bộ nhớ: 128 megabyte.
acbE4Lờ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 😇.
Trước khi vào bài, các bạn nhớ giúp mình điều này: với các hệ thống chấm giới hạn 1 giây, toàn bài chỉ nên lặp khoảng $(3 \to 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (lúc này hên xui). Đề cho 2 giây thì nhân 2 ngưỡng lên, 100 ms thì chia 10. Ngưỡng này là cho C/C++, còn Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn nữa nha.
Bài này $N \le 5 \cdot 10^4$ nên $N^2 = 25 \cdot 10^8$, gấp 25 lần ngưỡng cao nhất $10^8$. Vậy ngay khi đọc đề ta phải định hình: thuật toán cần từ $O(N \log N)$ trở xuống, còn từ $O(N^2)$ trở lên là chắc chắn TLE. Điều này rất quan trọng!
Giải thích ví dụ: xâu acbE có 4 kí tự đôi một khác nhau, nên cả xâu chính là xâu con thỏa mãn dài nhất ⇒ đáp án 4. Lấy thêm ví dụ abcabcbb: các xâu con như abc, bca, cab có độ dài 3 là thỏa mãn, còn mọi xâu con dài 4 đều có kí tự lặp ⇒ đáp án 3. Lưu ý chữ hoa và chữ thường là khác nhau (a khác A).
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn mọi xâu con – O(N⁴)
Mình luôn khuyên các bạn: với mọi bài, nếu chưa nghĩ ra cách tối ưu (hoặc nghĩ ra nhưng chưa chắc đúng) thì hãy làm vét cạn trước. Vét cạn tuy chạy lâu nhưng dễ cài đúng, nên ta dùng nó để kiểm tra cách tối ưu; làm vét cạn rồi cũng dễ thấy chỗ dở của nó để tối ưu; còn nếu không nghĩ ra cách tốt hơn thì vét cạn giúp vét được bao nhiêu điểm thì vét (thi theo thể thức IOI).
Cách cơ bản nhất: xét tất cả các xâu con liên tiếp theo độ dài giảm dần từ $N$ về $1$. Với mỗi xâu con, kiểm tra xem các kí tự trong đó có đôi một phân biệt không. Xâu con đầu tiên thỏa mãn chắc chắn là dài nhất (vì ta xét từ dài về ngắn) ⇒ in độ dài của nó và kết thúc luôn. Ví dụ với abcde, thứ tự xét là:
bcde
bcd
cde
bc
cd
de
b
c
d
e
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;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
for(int length = s.length(); length >= 1; --length){
int start = 0;
int finish = length - 1;
while(finish < (int)s.length()){
//cout << s.substr(start, length);
bool check = true;
for(int i = start; i <= finish; ++i){
for(int j = i + 1; j <= finish; ++j){
if(s[i] == s[j]){
check = false;
i = finish;
break;
}
}
}
if(check == true){
cout << length;
return 0;
}
start++;
finish++;
}
}
return 0;
}import sys
s = input().strip()
n = len(s)
for length in range(n, 0, -1):
start = 0
finish = length - 1
while finish < n:
check = True
i = start
while i <= finish:
for j in range(i + 1, finish + 1):
if s[i] == s[j]:
check = False
i = finish
break
i += 1
if check:
print(length)
sys.exit()
start += 1
finish += 1Giải thích một số chỗ trong code:
- 3 dòng đầu hàm
main(ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);) giúp tăng tốc nhập xuất của C++ (hiểu cơ bản là chocin/coutchạy nhanh gần bằng nhập xuất kiểu C). Bài nào nhập xuất nhiều như xâu dài tới $5 \cdot 10^4$ kí tự thì nên thêm 3 dòng này vào nhé. - Vòng
for lengthxét mọi độ dài từs.length()về 1.start,finishlà index bắt đầu và kết thúc của xâu con độ dàilength: ban đầustart = 0,finish = length - 1; điều kiệnfinish < s.length()để xâu con không vượt ra ngoài xâu gốc; xét xong thìstart++; finish++;để tịnh tiến sang xâu con kế tiếp. Dòngcout << s.substr(start, length);mình để comment, bạn nào muốn thì mở ra để xem lần lượt các xâu con được xét (substr(start, length)lấylengthkí tự bắt đầu từ indexstart). - Kiểm tra xâu con bằng 2 vòng
for i, jlồng nhau (giống thuật toán sắp xếp cơ bản hồi nhập môn): xét mọi cặp, gặp cặp trùng thìcheck = falsevà thoát khỏi cả 2 vòng lặp. Vìbreakchỉ thoát vòng gần nhất (vòngj), nên trước đó mình gáni = finish: quay về vòngi,i++thànhfinish + 1không còn thỏai <= finish⇒ vòngicũng dừng luôn.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ với $N$ là độ dài xâu.
- Thời gian: có khoảng $\frac{N(N+1)}{2}$ xâu con, xem như $O(N^2)$ (bỏ hằng số). Kiểm tra một xâu con độ dài $L$ tốn $\frac{L(L-1)}{2}$, xem như $O(L^2)$, mà $L$ lớn nhất bằng $N$. Trường hợp xấu nhất phải xét tới tận các xâu con độ dài 1, nên về lý thuyết là $O(N) + O(N^2 \cdot N^2) = O(N^4)$.
Với $N = 5 \cdot 10^4$ thì $N^4 = 5^4 \cdot 10^{16} = 6\,250\,000\,000\,000\,000\,000$, vượt quá xa ngưỡng $10^8$ ⇒ chắc chắn TLE.
set<char> (set tự bỏ phần tử trùng), rồi so se.size() với length: bằng nhau tức là không có kí tự trùng. Nhớ clear set trước khi xét xâu con kế tiếp. Set chỉ chứa tối đa $K = 52$ kí tự (26 thường + 26 hoa) nên mỗi lần chèn tốn $O(\log K)$, $\log_2 52$ chưa tới 6. Khi đó bước kiểm tra chỉ còn $O(L \log K)$ và cả thuật toán là $O(N^3 \log K)$.Cách 2Hai con trỏ + map – O(N log K)
Bài này có thể giải với $O(N \log K)$ ($K$ là số kí tự phân biệt, tối đa 52), thậm chí $O(N)$. Để làm được thì cần kĩ thuật hai con trỏ (Two Pointers) kết hợp với map hoặc mảng đánh dấu.
Ý tưởng: không xét mọi xâu con từ dài tới ngắn nữa, mà duyệt một lần từ đầu tới cuối xâu, luôn giữ một xâu con hợp lệ (toàn kí tự phân biệt) bắt đầu từ start và kết thúc tại kí tự đang xét $s[i]$, đồng thời cập nhật LengthMax.
- Dùng
map<char, int> mp: key là kí tự, value là vị trí gần nhất kí tự đó xuất hiện. - Xét $s[i]$: nếu chưa có trong
mpthì đưa vào kèm vị trí $i$. - Nếu đã có, gọi vị trí cũ là
idx:idx >= start: $s[i]$ trùng với $s[idx]$ nằm trong xâu con đang giữ, nên xâu con này không thể nhận thêm $s[i]$. Xâu con hợp lệ dài nhất từstartlà từstarttớii - 1, độ dàii - start⇒ cập nhậtLengthMax. Rồi dờistart = idx + 1để bỏ kí tự trùng cũ đi.idx < start: lần xuất hiện cũ đã nằm ngoài xâu con đang giữ, nên vẫn nhận $s[i]$ bình thường.- Cả 2 trường hợp đều phải cập nhật lại vị trí gần nhất của $s[i]$ là $i$.
- Cuối cùng, xâu con từ
starttới hết xâu có thể chưa được tính (vì không gặp kí tự trùng nào để kích hoạt việc cập nhật), nên phải so thêms.length() - startvớiLengthMax.
start++ từng bước rồi xét lại. Mình thấy như vậy không tối ưu: nếu đoạn start..i-1 dài $L$ thì đoạn start+1..i-1 chỉ là xâu con của nó, dài $L-1$, chắc chắn không tốt hơn, xét làm gì? Mà chừng nào còn chứa $s[idx]$ thì đoạn đó cũng không nhận được $s[i]$. Vì vậy cho start = idx + 1 luôn để bỏ kí tự trùng, nhận $s[i]$ vào rồi xét tiếp $s[i+1]$.Ở đây start là con trỏ thứ nhất, còn i chạy phía trước là con trỏ thứ hai. Cả hai chỉ đi tới, không bao giờ lùi.
Minh hoạ hai con trỏ
Em nhập xâu (chỉ chữ cái) rồi bấm Tiếp để xem "cửa sổ" [start..i] trượt như thế nào. Ô xanh dương là xâu con hợp lệ đang giữ, ô vàng là $s[i]$ đang xét, bảng bên dưới là vị trí gần nhất của từng kí tự (chính là mp hay mảng a):
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;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
map<char, int> mp;
int start = 0;
int LengthMax = 0;
for(int i = 0; i < (int)s.length(); ++i){
auto it = mp.find(s[i]);
if(it == mp.end()){
mp.insert({s[i], i});
}
else{
int idx = it->second;
if(idx >= start){
LengthMax = max(LengthMax, i - start);
start = idx + 1;
}
it->second = i;
}
}
LengthMax = max(LengthMax, (int)s.length() - start);
cout << LengthMax;
return 0;
}s = input().strip()
mp = {}
start = 0
LengthMax = 0
for i in range(len(s)):
if s[i] not in mp:
mp[s[i]] = i
else:
idx = mp[s[i]]
if idx >= start:
LengthMax = max(LengthMax, i - start)
start = idx + 1
mp[s[i]] = i
LengthMax = max(LengthMax, len(s) - start)
print(LengthMax)Giải thích một số chỗ trong code:
auto it = mp.find(s[i]);mình dùngautođể trình biên dịch tự xác định kiểu, viết rõ ra thì làmap<char, int>::iterator it;nhé.- Chỗ
mp.insert({s[i], i});các bạn cũng có thể viếtmp[s[i]] = i;. Tuy nhiên quan điểm cá nhân của mình là không muốn đụng vô cáioperator []của map vì dễ sai chết người lắm 😅 (chỉ cần "đọc"mp[x]vớixchưa có là map tự chèn thêm phần tửxvào), bạn nào muốn thì tìm hiểu thêm vụ này nha.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho xâu + $O(K)$ cho map.
- Thời gian: $O(N \log K)$. Mỗi kí tự $s[i]$ cần tìm trong map ($O(\log K)$) và có thể chèn vào map ($O(\log K)$ + chi phí cân bằng cây, vì map được cài bằng cây nhị phân tìm kiếm cân bằng; ở đây mình bỏ qua chi phí cân bằng cây). $K$ là số phần tử map chứa, tối đa chỉ 52 (map không chứa key trùng).
Với $N = 5 \cdot 10^4$, $K = 52$: khoảng $5 \cdot 10^4 \cdot 6 = 3 \cdot 10^5$ (làm tròn $\log_2 52$ lên 6), ít hơn ngưỡng TLE cả trăm lần, yên tâm nhé.
Cách 3Hai con trỏ + mảng đánh dấu – O(N)
Thậm chí ta còn tối ưu hơn bằng mảng đánh dấu. Chữ in hoa A…Z có mã ASCII từ 65 đến 90, chữ thường a…z từ 97 đến 122. Vậy tạo mảng int a[123] (index 0 đến 122), chỉ dùng các ô 65–90 và 97–122, các ô khác bỏ không. a[c] là vị trí gần nhất của kí tự có mã ASCII c.
- Ban đầu gán tất cả
a[c] = -1. Chọn $-1$ để biết rõ đó không phải index hợp lệ; đừng chọn $0$ vì index hợp lệ cũng tính từ $0$, sẽ nhầm. - Xét $s[i]$: nếu
a[s[i]] == -1thì kí tự chưa xuất hiện, gána[s[i]] = i. Ngược lại thìidx = a[s[i]]và mọi thứ y như cách 2.
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;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
int a[123];
memset(a, -1, sizeof(a));
int start = 0;
int LengthMax = 0;
for(int i = 0; i < (int)s.length(); ++i){
if(a[s[i]] == -1){
a[s[i]] = i;
}
else{
int idx = a[s[i]];
if(idx >= start){
LengthMax = max(LengthMax, i - start);
start = idx + 1;
}
a[s[i]] = i;
}
}
LengthMax = max(LengthMax, (int)s.length() - start);
cout << LengthMax;
return 0;
}s = input().strip()
a = [-1] * 123
start = 0
LengthMax = 0
for i in range(len(s)):
c = ord(s[i])
if a[c] == -1:
a[c] = i
else:
idx = a[c]
if idx >= start:
LengthMax = max(LengthMax, i - start)
start = idx + 1
a[c] = i
LengthMax = max(LengthMax, len(s) - start)
print(LengthMax)Giải thích một số chỗ trong code:
memset(a, -1, sizeof(a));gán giá trị $-1$ cho toàn bộ vùng nhớ của mảnga. Không dùng memset thì tự viết vòng lặp gána[i] = -1cũng được, nhưng memset gọn và tác động thẳng vào vùng nhớ nên về lý thuyết nhanh hơn (muốn thấy khác biệt thì thử với mảng cỡ vài triệu phần tử trở lên).- Sao không khai báo mảng 52 phần tử cho đỡ phí? Vì khi đó mỗi kí tự lại phải xét thêm
if(s[i] >= 'A' && s[i] <= 'Z')thì dùnga[s[i] - 'A'], ngược lạia[s[i] - 'a' + 26], tức là thêm phép so sánh và phép tính cho cả $5 \cdot 10^4$ kí tự. Mình chịu tốn thêm vài ô nhớ mà cứ gọi thẳnga[s[i]]là xong. Bộ nhớ thường cho rất dư dả, chỉ thời gian chạy mới bị làm gắt thôi. Đây là một sự đánh đổi: tốn thêm bộ nhớ để chạy nhanh hơn.
ord(s[i]) để đổi kí tự ra mã ASCII.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho xâu + $O(K)$ cho mảng đánh dấu, ở đây $K = 123$.
- Thời gian: $O(N)$ đọc xâu + $O(K)$ cho memset + $O(N)$ xử lý chính (mỗi lần truy cập
a[s[i]]chỉ $O(1)$) ⇒ $O(\max(N, K))$.
Với $N = 5 \cdot 10^4$ chỉ tốn $5 \cdot 10^4$ lần lặp, tốt hơn cách dùng map ($3 \cdot 10^5$) tầm 6 lần.
map như cách 2 nhé.set – khớp hết. Với xâu $5 \cdot 10^4$ chữ cái ngẫu nhiên: cách 2 và cách 3 (C++) đều chạy dưới 0.03 giây, bản Python dưới 0.1 giây; còn cách 1 chạy hơn 30 giây vẫn chưa xong ⇒ TLE đúng như phân tích.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét