Table of Contents

ExplanationImplementation

Official Editorial

Explanation

Since the MEX can be at most 2 when there is a substring that contains a 0 and 1, there's only 3 possible cases. If there are no zeros, then the MEX is 0, since all substrings would be missing a 0. If all zeros are adjacent to one another, we can cut the entire sequence out, leaving a MEX of 1. The other groups, all comprised of ones would have a MEX of 0. Leaving the answer to be max(0,1)=1max(0, 1) = 1. Lastly, if there are zeros and they're not adjacent to one another, then a substring like 0,1{0, 1} must exist, resulting in a MEX of 2.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <algorithm>
#include <iostream>
using namespace std;


int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		string s;
		cin >> s;

Java

import java.io.*;


public class MinMexCut {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(read.readLine());
		for (int i = 0; i < t; i++) {
			String s = read.readLine();
			// find the number of zeros
			int zeros = s.length() - s.replace("0", "").length();

Python

for _ in range(int(input())):
	s = input()
	# find the number of zeros
	zeros = s.count("0")


	if zeros == 0:
		print(0)  # no zeros, the answer is 0
	else:
		# first and last occurrences of zero
		l = s.find("0")
		r = s.rfind("0")
		# if they're all adjacent to one another
		print(1 if r - l + 1 == zeros else 2)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum