11389. Huseyn’s game

Huseyn has a string consisting of characters 0 and 1. To entertain himself, he came up with the following game. Huseyn can perform one of two operations on the string:

· append 0 to the left end, and 1 to the right end;

· append 0 to the right end, and 1 to the left end;

For example, from the string 010, Huseyn can obtain 00101 or 10100.

You are given a string obtained after all of Huseyn's operations (it is possible that he did not perform any operation). Determine the smallest possible length the string could have initially had.

Input. A single string of length no more than 10⁵, consisting only of characters 0 and 1.

Output. Print the smallest possible length of the string that Huseyn could have initially had.

Sample input 1	Sample output 1
01010010	8
Sample input 2	Sample output 2
1001110	1

SOLUTION

two pointers

Algorithm analysis

Let’s consider the input string s – the resulting string after Huseyn has performed all operations. Initialize two pointers: i = 0 at the start of the string and j = n – 1 at the end.

If s_i ≠ s_j, then the characters at the ends of the string are different: either 0 on the left and 1 on the right, or 1 on the left and 0 on the right. This means the previous string could have been extended by applying one of the specified operations. In this case, move both pointers i and j one position towards each other and check again whether the substring s[i ... j] could have been obtained through Huseyn’s operations.

As soon as the current substring s[i ... j] satisfies s_i = s_j, it can no longer be produced by the given operations. Print its length – this is the original string that Huseyn had.

Example

Let’s perform Huseyn’s operations in reverse order.

The string s = “1” was originally the one Huseyn had.

Algorithm realization

Read the input string and calculate its length, storing it in the variable res.

cin >> s;

res = s.size();

Initialize two pointers: i = 0 at the start and j = n – 1 at the end of the string.

i = 0; j = s.size() - 1;

If s_i ≠ s_j, then the characters at the ends of the string are different. Huseyn could have obtained the substring s[i ... j] from the substring s[i + 1 ... j – 1].

while ((i < j) && (s[i] != s[j]))

{

Move both pointers i and j one position towards each other and decrease the current size res of the substring s[i ... j].

i++; j--;

res -= 2;

}

Print the answer.

cout << res << endl;