R02195
필수 부품 최소 상자
실버 I레이팅
의견: 0
설명
조립 라인 위에 부품들이 소문자 알파벳으로 표기되어 문자열 \(s\)로 일렬로 놓여 있다. 각 알파벳은 부품의 종류를 뜻한다.
주문서 \(t\)에는 필요한 부품이 (중복을 포함해) 적혀 있다. \(s\)의 연속한 구간 하나만 상자에 담아 주문서의 모든 부품을 (각 종류를 필요한 개수 이상) 충족시키려 할 때, 담아야 하는 가장 짧은 연속 구간의 길이를 구하여라. 충족이 불가능하면 \(0\)을 출력한다.
제약
\(1 \le |t| \le |s| \le 1500\)
입력 형식
첫째 줄에 부품 배열을 나타내는 문자열 \(s\)가 주어진다.
둘째 줄에 주문서를 나타내는 문자열 \(t\)가 주어진다.
두 문자열은 모두 소문자 알파벳으로만 이루어진다.
출력 형식
주문서를 충족하는 가장 짧은 연속 구간의 길이를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 | \(1 \le |s| \le 200\) |
Subtask 2 | 60점 | 추가 제약이 없다. |
예제 1
입력
adobecodebanc
abc
출력
4
설명
\(a,b,c\)를 모두 포함하는 가장 짧은 부분문자열은 "banc"로 길이 \(4\)이다.
예제 2
입력
aa
aaa
출력
0
설명
필요한 "a" \(3\)개를 채울 수 없으므로 \(0\)을 출력한다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
필수 부품 최소 상자
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
필수 부품 최소 상자
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기