FULLSTR - Chuỗi con đầy đủ
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho chuỗi ký tự ~s~ gồm các ký tự latin in hoa ( A đến Z ). Ta gọi một đoạn liên tiếp các ký tự của ~s~ có mặt đủ ~26~ ký tự latin in hoa là một chuỗi con đầy đủ. Hãy tìm một chuỗi con đầy đủ của ~s~ có độ dài ngắn nhất.
Input
- Một dòng duy nhất chứa chuỗi ~s~.
Giới hạn:
- Độ dài chuỗi ~s~ không quá ~10^5~.
Output
- Một số nguyên dương duy nhất là độ dài chuỗi con đầy đủ ngắn nhất. Nếu không có chuỗi con đầy đủ thì ghi ra ~-1~.
Sample
Input #1
ABCDEFHGJIKLMNOPQRUVXYZTSASCWO
Output #1
28
Hint
- Đoạn tô đậm và gạch chân sau: ABCDEFHGJIKLMNOPQRUVXYZTSASCWO có độ dài ~28~ ký tự và có mặt đủ ~26~ ký tự latin in hoa.
Problem source: Chuyên Sơn La Online Judge
Bình luận
Cách làm của mình dùng của sổ trươt : 1 thằng left=0 để làm mốc trái , right chạy từ 0 đến hết độ dài của xâu , unique=0 để đánh dấu xem đủ 26 kí tự chưa ,và 1 mảng xem đã thăm chưa visited[100] kiểu integer để nhớ số lần thăm ->chạy vào vòng for right nếu +)++visted[s[right]-'A']==1 thì unique sẽ được cộng lên 1 , cộng tiền tố là hợp lí vì để nó chạy vào điều kiện nó sẽ tự cộng visited[vị trí đó] lên 1 +1 vòng while(unique==26): -Cập nhật lại độ dài len=min(len,right-left+1); - Giờ phải cập nhật lại thằng left vì biết đâu thằng left+ thêm 1 thì unique vẫn bằng 26 --Nếu --visited[s[left]-'A']==0 thì unique sẽ phải trừ đi 1 (Bạn hãy nhìn vào ví dụ đề bài ban đầu len sẽ , tính từ A đầu tiên đến thằng W , lúc này visited[A] =2 nên nếu left nhỉnh lên thằng B thì visited[A] vẫn chưa bằng 0 nên unique vẫn là 26 ) -- Cập nhật lại thằng left : left++; Thế là ac nhé mọi người