[Solution] Sorted Substrings CodeChef Solution

Problem

You have a binary string $S$. You can perform the following operation on $S$:

• Select any substring $S_{L \dots R}$ $(1 \le L \le R \le |S|)$ which is sorted and remove it from $S$. (Both the left and right halves are concatenated after performing the operation)

For e.g. if $S = 100011000$, we can perform the following operation: $100\underline{011}000 \rightarrow 100000$

Find the minimum number of operations required so that the final binary string $S$ is sorted.

Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the length of the binary string $S$.
• The second line of each test case contains a binary string $S$ of length $N$ containing $0$s and $1$s only.

Output Format

For each test case, output the minimum number of operations required so that the final binary string $S$ is sorted.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Explanation:

Test case $1$: The binary string is already sorted, so we need no operations.

Test case $2$: We can use one operation to remove the sorted substring $S_{2 \dots 4} = 111$. Thus, the remaining string $00$ is sorted.

Test case $3$: We can use one operation to remove the sorted substring $S_{2 \dots 2} = 0$. Thus, the remaining string $1$ is sorted.