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

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

• Java
• Python

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.io.PrintWriter;
	import java.io.IOException;
	public class Main{
	public static int getTernaryString(String s) {
	int count = Integer.MAX_VALUE;
	int[] index = new int[3];
	int left = 0;
	for (int right = 0; right < s.length(); right++) {
	index[s.charAt(right) - 49] += 1;
	while (index[s.charAt(left) - 49] > 1) {
	index[s.charAt(left) - 49] -= 1;
	left++;
	}
	if (index[0] != 0 && index[1] != 0 && index[2] != 0) {
	count = Math.min(count, right -left + 1);
	}
	}
	return count == Integer.MAX_VALUE ? 0 : count;
	}
	public static void main(String []args) throws IOException {
	BufferedReader br = new BufferedReader(
	new InputStreamReader(System.in));
	PrintWriter wr = new PrintWriter(System.out);
	int testCase = Integer.parseInt(br.readLine());
	while (testCase-- > 0 ) {
	wr.println(getTernaryString(br.readLine()));
	}
	wr.close();
	br.close();
	}
	}

view raw TernaryString.java hosted with ❤ by GitHub

	from sys import stdin, stdout, maxsize
	def get_ternary_string(input_text: str) -> int:
	index = [0] * 3
	count = maxsize
	left = 0
	for right in range(0, len(input_text)):
	pos = ord(input_text[right]) - 49
	index[pos] += 1
	while index[ord(input_text[left]) - 49 ] > 1 :
	index[ord(input_text[left]) - 49] -= 1
	left += 1
	if index[0] != 0 and index[1] != 0 and index[2] != 0:
	count = min(count, right - left + 1)
	return 0 if count == maxsize else count
	test_cases = int(stdin.readline().strip())
	while test_cases > 0:
	input_text = stdin.readline().strip()
	print(get_ternary_string(input_text))
	test_cases -= 1

view raw ternary_string.py hosted with ❤ by GitHub

Complexity

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

Footnotes

---

1. Codeforces problem 1354 B

   ↩

---