Educational Codeforces Round 87(Rated for Div. 2)B. Ternary String 슬라이딩 윈도우 보드 문제
A contiguous substring of string s is a string that can be obtained from s by removing some (possibly zero) characters from the beginning of s and some (possibly zero) characters from the end of s.
Input The first line contains one integer t (1≤t≤20000) — the number of test cases.
Each test case consists of one line containing the string s (1≤|s|≤200000). It is guaranteed that each character of s is either 1, 2, or 3.
The sum of lengths of all strings in all test cases does not exceed 200000.
Output For each test case, print one integer — the length of the shortest contiguous substring of s containing all three types of characters at least once. If there is no such substring, print 0 instead.
Example inputCopy 7 123 12222133333332 112233 332211 12121212 333333 31121 outputCopy 3 3 4 4 0 0 4 Note Consider the example test:
In the first test case, the substring 123 can be used.
In the second test case, the substring 213 can be used.
In the third test case, the substring 1223 can be used.
In the fourth test case, the substring 3221 can be used.
In the fifth test case, there is no character 3 in s.
In the sixth test case, there is no character 1 in s.
In the seventh test case, the substring 3112 can be used. 여러 개의 질문, 각각 2e 5 2e5 2e5의 문자열 S S, S S S는 숫자 ′1′, ′2′, ′3′'1','2','3'′1′, ′2′, ′3′로 연속된 하위 문자열 s u b S subs를 구합니다. s u b S subs가 가장 짧고 ′1′, ′2′, ′3′1, `3′1, `3′1, `2′2, 모든 창의 유일한 슬라이딩 보드:
//#define debug
#ifdef debug
#include
#include "/home/majiao/mb.h"
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAXN ((int)2e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define QAQ (0)
using namespace std;
#ifdef debug
#define show(x...) \
do { \
cout << "\033[31;1m " << #x << " -> "; \
err(x); \
} while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
int n, m, Q, K;
char buf[MAXN];
#define INC (cnt[(int)'1'] && cnt[(int)'2'] && cnt[(int)'3'])
int main() {
#ifdef debug
freopen("test", "r", stdin);
clock_t stime = clock();
#endif
scanf("%d ", &Q);
while(Q--) {
scanf("%s ", buf);
int cnt[128] = { 0 };
int lef = 0, rig = -1, ans = 0x3f3f3f3f;
while(buf[lef]) {
while(buf[rig+1] && !INC) {
cnt[(int)buf[rig+1]] ++;
rig ++;
}
// show(lef, rig, cnt[(int)'1'], cnt[(int)'2'], cnt[(int)'3']);
if(INC)
ans = min(ans, rig-lef+1);
cnt[(int)buf[lef]] --;
lef ++;
}
printf("%d
", ans==0x3f3f3f3f ? 0 : ans);
}
#ifdef debug
clock_t etime = clock();
printf("rum time: %lf
",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2020 우 객 여름 다 교 훈련소 (6 차 전) K - Bag [슬라이딩 창]제목 링크:https://ac.nowcoder.com/acm/contest/5671/K 제목 k - bag 를 1 ~ k 로 정의 하 는 여러 개의 전체 배열 로 구 성 된 서열, part - k - bag 는 k ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.