Random Wits

Life is too short for a diary

$ random wits
├── tags

├── bookshelf

├── resources

├── quotes

├── habits

└── about





Thu 04 Nov 2021

Ternary String solution Codeforces - 1354B

Tags: codeforces two pointers java python

Ternary string is an interesting problem that could be solved using two pointers techniques. It’s a convenient way to keep track of multiple indices. This helps in making decisions based on two values.

Problem Statement

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. 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.1

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

7
123
12222133333332
112233
332211
12121212
333333
31121

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.

3
3
4
4
0
0
4

Two pointers

We can start with two pointers; left and right. Index array is used to keep track of the frequency of each occurrence of characters in string s. We can safely increment left pointer till index[s[left]] is greater than 1. The output is the minimum value of the window (right - left + 1);

Implementation

Complexity

Time Complexity is \(\theta(n)\)


comments powered by Disqus