Algorithm


A. Antipalindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A string is a palindrome if it reads the same from the left to the right and from the right to the left. For example, the strings "kek", "abacaba", "r" and "papicipap" are palindromes, while the strings "abb" and "iq" are not.

A substring s[lr]�[�…�] (1lr|s|1 ≤ � ≤ � ≤ |�|) of a string s=s1s2s|s|� = �1�2…�|�| is the string slsl+1sr���� + 1…��.

Anna does not like palindromes, so she makes her friends call her Ann. She also changes all the words she reads in a similar way. Namely, each word s is changed into its longest substring that is not a palindrome. If all the substrings of s are palindromes, she skips the word at all.

Some time ago Ann read the word s. What is the word she changed it into?

Input

The first line contains a non-empty string s with length at most 5050 characters, containing lowercase English letters only.

Output

If there is such a substring in s that is not a palindrome, print the maximum length of such a substring. Otherwise print 00.

Note that there can be multiple longest substrings that are not palindromes, but their length is unique.

Examples
input
Copy
mew
output
Copy
3
input
Copy
wuffuw
output
Copy
5
input
Copy
qqqqqqqq
output
Copy
0
Note

"mew" is not a palindrome, so the longest substring of it that is not a palindrome, is the string "mew" itself. Thus, the answer for the first example is 33.

The string "uffuw" is one of the longest non-palindrome substrings (of length 55) of the string "wuffuw", so the answer for the second example is 55.

All substrings of the string "qqqqqqqq" consist of equal characters so they are palindromes. This way, there are no non-palindrome substrings. Thus, the answer for the third example is 00.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int main() {
  string s;
  cin >> s;

  int mx = 0;
  for(int i = 0; i < s.length(); ++i) {
  	for(int j = 1; j <= s.length(); ++j) {
  		string tmp = s.substr(i, j), rev = tmp;
  		reverse(rev.begin(), rev.end());
  		if(tmp != rev)
  			mx = max(mx, int(tmp.length()));
  	}
  }

  cout << mx << endl;

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
mew

Output

x
+
cmd
3
Advertisements

Demonstration


Codeforces Solution-A. Antipalindrome-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+