You have a binary string (each character is either '0' or '1') of length $n$. You want to pop characters from this string as much as possible, by popping we mean you can do one of the following operations:
What is the maximum number of times you can pop from this string such that after doing all the pop operations, the first and the last characters remain the same as the first and the last characters from the initial string, respectively?
The first line of input contains a single integer $n$ $(1 \le n \le 10^5)$, the length of the string.
The second line contains a binary string of length $n$.
Print a single integer, the maximum number of times you can pop such that the above condition is satisfied.
In the first example, we can pop the first character twice and the last character once, resulting in the string "10". In total we made 3 pop operations.
Note that for example, we can't pop the first 3 characters, because we will end up with "00" which has a different first character from the initial string "11100".
| Input | Output |
|---|---|
5 11100 Copy
|
3 Copy
|
If the first and last characters are both zeroes or both ones, then we can pop all characters except the first character, so the answer is $n-1$.
If the first character is zero and the last character is one(or vice versa), then let us look at the first character that is equal to one from the left, that character has a zero behind, so we pop all characters except for those two characters and the answer is $n-2$.
#include <bits/stdc++.h>
using namespace std;
int const N = 200000;
char s[N + 1];
int main(){
int n;
scanf("%d%s", &n, s);
printf("%d\n", n - 1 - (s[0] != s[n - 1]));
}