codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1354B.md (1702B)


      1 Source: https://codeforces.com/problemset/problem/1354/B
      2 
      3 B. Ternary String
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a string $s$ such that each its character is either 1, 2, or 3. You have to choose the shortest contiguous substring of $s$ such that it contains each of these three characters at least once.
     22 
     23 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$.
     24 
     25 Input
     26 
     27 The first line contains one integer $t$ ($1 \le t \le 20000$) — the number of test cases.
     28 
     29 Each test case consists of one line containing the string $s$ ($1 \le |s| \le 200000$). It is guaranteed that each character of $s$ is either 1, 2, or 3.
     30 
     31 The sum of lengths of all strings in all test cases does not exceed $200000$.
     32 
     33 Output
     34 
     35 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.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 7
     43 123
     44 12222133333332
     45 112233
     46 332211
     47 12121212
     48 333333
     49 31121
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 3
     56 3
     57 4
     58 4
     59 0
     60 0
     61 4
     62 ```
     63 
     64 Note
     65 
     66 Consider the example test:
     67 
     68 In the first test case, the substring 123 can be used.
     69 
     70 In the second test case, the substring 213 can be used.
     71 
     72 In the third test case, the substring 1223 can be used.
     73 
     74 In the fourth test case, the substring 3221 can be used.
     75 
     76 In the fifth test case, there is no character 3 in $s$.
     77 
     78 In the sixth test case, there is no character 1 in $s$.
     79 
     80 In the seventh test case, the substring 3112 can be used.