#88 Making a Monochrome String

Loading problem...

Preparing the statement, recent submissions, and submit form.

#88 Making a Monochrome String | DOJ

Time limit: 1000 ms
Python time limit: 3000 ms
Memory limit: 1024 MB
Checker: DIFF
Solve threshold: 100

Statement

You are given a binary string $S$ of length $N$ . A binary string is a string whose every character is either $`0`$ or $`1`$ .

In one operation, you may choose a non-empty contiguous substring $T$ of the current string such that the number of $`0`$ s in $T$ is equal to the number of $`1`$ s in $T$ , and delete it. After deletion, the remaining prefix and suffix are concatenated.

A string is called monochrome if it satisfies one of the following conditions.

The string is empty.
Every character of the string is $`0`$ .
Every character of the string is $`1`$ .

Find the minimum number of operations required to make $S$ monochrome.

Input

The input is given in the following format.

$N$ $S$

Output

Print the minimum number of operations required to make $S$ monochrome.

Constraints

$1 \le N \le 200\,000$ .
$S$ is a binary string of length $N$ .

Subtasks

#	Score	Constraints
1	20	$N \le 20$ .
2	30	$N \le 5\,000$ .
3	50	No additional constraints.

Samples

Sample 1

Input

4
0101

Output

Since the number of 0s and 1s in the entire string are both $2$ , the entire string can be deleted at once.

Sample 2

Input

5
00011

Output

Leaving the first 0 and deleting the substring 0011 results in the monochromatic string 0.

Sample 3

Input

9
100010001

Output

A monochromatic string can be made with $3$ operations, and it can be proven that is it the optimal answer.

Sample 4

Input

5
00000

Output

All characters are 0 from the beginning, so it is already a monochromatic string.

Editorial

View editorial