[Solution] Flipping Failure CodeChef Solution

Problem

Chef has a binary string $S$ with him and he wants to modify it using the following two types of operations -

• Type 1 : Choose any two indices $i$ and $j$ such that $1 \leq i, j \leq |S|$ and swap $S_i$ and $S_j$. This operation costs $1$ rupee and can be performed any number of times.
• Type 2 : Choose any prefix of length $i$, where $1 \leq i \leq |S|$, and reverse this prefix of the binary string. This operation is free of cost and can be performed at most once.

Chef wants to obtain the lexicographically smallest string. Can you help him find the minimum cost to obtain the lexicographically smallest string?

Note:

• $|S|$ denotes the length of the string $S$.
• A string $A$ is lexicographically smaller than string $B$, if $A_i \lt B_i$, where $i$ is the first index where $A$ and $B$ differ.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• Each test case consists of a single line of input denoting $S$, the original string.

Output Format

For each test case, output the minimum cost to obtain the lexicographically minimal string.

Explanation:

Test case 1: You can perform an operation of Type 1 by choosing $i = 2$ and $j = 3$. So from $1\textcolor{violet}{0}\textcolor{olive}{1}0$, you get $1100$, and it has cost you $1$ rupee so far. Then, you perform an operation of Type 2, by choosing $i = 4$. So you reverse the entire string, and so from $\textcolor{red}{1100}$, you get $0011$. This operation is free of cost. This is the lexicographically smallest string that you can achieve, and it cost us $1$ rupee to get there. So the answer is $1$.

Test case 2: You can perform an operation of Type 2, by choosing $i = 2$. So you reverse the prefix of length 2, and so from $\textcolor{red}{10}1$, you get $011$. This operation is free of cost. This is the lexicographically smallest string that you can achieve, and it cost us $0$ rupees to get there. So the answer is $0$.

Test case 3: You can perform an operation of Type 1 by choosing $i = 4$ and $j = 6$. So from $100\textcolor{violet}{1}0\textcolor{olive}{0}$, you get $100001$, and it has cost you $1$ rupee so far. Then, you perform an operation of Type 2, by choosing $i = 5$. So you reverse the prefix of length 5, and so from $\textcolor{red}{10000}1$, you get $000011$. This operation is free of cost. This is the lexicographically smallest string that you can achieve, and it cost us $1$ rupee to get there. So the answer is $1$.