Cửa sổ trượt co dãn 2
Đoạn Con Ngắn Nhất Tổng Lớn Hơn Hoặc Bằng S
Nộp bàiPoint: 1
Cho dãy số nguyên dương A gồm N phần tử và số nguyên dương S.
Hãy tìm độ dài của đoạn con liên tiếp NGẮN NHẤT có tổng lớn hơn hoặc bằng S.
Nếu không có đoạn nào thỏa mãn, in ra 0.
Input:
Dòng 1: N, S (1 <= N <= 10^5, 1 <= S <= 10^9).
Dòng 2: N số nguyên dương A[i].
Giới hạn:
1 <= N <= 10^5
1 <= S <= 10^14
1 <= A[i] <= 10^9
Output:
- Độ dài ngắn nhất tìm được.
Ví dụ 1:
Input:
6 15
2 1 5 2 8 1
Output:
2
Ví dụ 2:
Input:
5 100
1 2 3 4 5
Output:
0
Đếm Đoạn Con Có Tổng Nhỏ Hơn S
Nộp bàiPoint: 1
Cho dãy số nguyên dương A và số nguyên S.
Hãy đếm số lượng các đoạn con liên tiếp có tổng nhỏ hơn hẳn S.
Input:
Dòng 1: N, S.
Dòng 2: N số nguyên A[i].
Giới hạn:
1 <= N <= 10^5
1 <= S <= 10^14
1 <= A[i] <= 10^9
Output:
- Số lượng đoạn con thỏa mãn.
Ví dụ 1:
Input:
4 5
1 2 3 4
Output:
5
Ví dụ 2:
Input:
3 100
10 20 30
Output:
6
Tích Nhỏ Hơn K
Nộp bàiPoint: 1
Cho dãy số nguyên dương A và số nguyên K.
Hãy đếm số lượng đoạn con liên tiếp có tích các phần tử nhỏ hơn hẳn K.
Input:
Dòng 1: N, K (K <= 10^9).
Dòng 2: N số nguyên A[i].
Giới hạn:
1 <= N <= 10^5
1 <= K <= 10^18
1 <= A[i] <= 10^9
Output:
- Số lượng đoạn con thỏa mãn.
Ví dụ 1:
Input:
4 10
1 2 3 4
Output:
7
Ví dụ 2:
Input:
3 1
10 20 30
Output:
0
Dãy Số 1 Dài Nhất (Được Đổi K Số 0)
Nộp bàiPoint: 1
Cho dãy số A chỉ gồm 0 và 1, và số nguyên K.
Bạn được phép đổi tối đa K số 0 thành số 1.
Hỏi dãy số 1 liên tiếp dài nhất có thể đạt được là bao nhiêu?
Input:
Dòng 1: N, K.
Dòng 2: N số nguyên A[i] (0 hoặc 1).
Giới hạn:
1 <= N <= 10^5
0 <= K <= N
Output:
- Độ dài dãy số 1 dài nhất.
Ví dụ 1:
Input:
6 2
1 0 0 1 1 0
Output:
5
Ví dụ 2:
Input:
5 0
0 0 0 0 0
Output:
0
Chuỗi Con Không Lặp Ký Tự
Nộp bàiPoint: 1
Cho chuỗi S. Hãy tìm độ dài của chuỗi con liên tiếp dài nhất mà không có ký tự nào bị lặp lại.
Input:
- Dòng 1: Chuỗi S.
Giới hạn:
Độ dài S <= 10^5
S gồm các chữ cái in thường, in hoa, số và ký tự đặc biệt.
Output:
- Độ dài dài nhất.
Ví dụ 1:
Input:
abcabcbb
Output:
3
Ví dụ 2:
Input:
bbbbb
Output:
1
Hái Quả (Max 2 Loại)
Nộp bàiPoint: 1
Bạn đang đứng trước một hàng cây, cây thứ i có loại quả là A[i].
Bạn chỉ mang theo 2 cái giỏ, mỗi giỏ chỉ đựng được 1 loại quả.
Bạn muốn hái quả ở một dãy cây liên tiếp sao cho số lượng cây hái được là nhiều nhất (tức là đoạn con dài nhất chỉ chứa tối đa 2 loại quả khác nhau).
Hãy tìm độ dài đó.
Input:
Dòng 1: N.
Dòng 2: N số nguyên A[i] biểu thị loại quả.
Giới hạn:
1 <= N <= 10^5
0 <= A[i] < N
Output:
- Số cây hái được nhiều nhất.
Ví dụ 1:
Input:
5
1 2 1 3 2
Output:
3
Ví dụ 2:
Input:
6
0 1 2 2 2 1
Output:
5
Đoạn Con Ngắn Nhất Chứa Ít Nhất K Loại
Nộp bàiPoint: 1
Cho dãy số A và số K.
Tìm độ dài của đoạn con liên tiếp NGẮN NHẤT chứa ít nhất K loại số khác nhau.
Nếu không có, in ra 0.
Input:
Dòng 1: N, K.
Dòng 2: N số nguyên A[i].
Giới hạn:
1 <= N <= 10^5
1 <= K <= N
1 <= A[i] <= 10^5
Output:
- Độ dài ngắn nhất hoặc 0.
Ví dụ 1:
Input:
6 3
1 2 2 3 1 4
Output:
3
Ví dụ 2:
Input:
4 5
1 2 3 4
Output:
0
Chuỗi Con Chứa Đủ Bộ Ký Tự (Min Window)
Nộp bàiPoint: 1
Cho chuỗi S và chuỗi T.
Hãy tìm độ dài của chuỗi con liên tiếp ngắn nhất trong S sao cho nó chứa tất cả các ký tự của chuỗi T (bao gồm cả số lần xuất hiện).
Ví dụ T="AABC" thì đoạn con phải có ít nhất 2 chữ A, 1 chữ B, 1 chữ C.
Nếu không tìm thấy, in ra 0.
Input:
Dòng 1: Chuỗi S.
Dòng 2: Chuỗi T.
Giới hạn:
Độ dài S, T <= 10^5
S, T gồm các chữ cái in hoa/thường.
Output:
- Độ dài ngắn nhất tìm được.
Ví dụ 1:
Input:
ADOBECODEBANC
ABC
Output:
4
Ví dụ 2:
Input:
A
AA
Output:
0