Good String | Practice Problems

Good String

★★★★★

3.7

3 votes

string, Easy

Details

Submissions

Discussion

Editorial

Problem

A string is called a $Good$ string if it has the following properties:

The length of the string is >=2
The first and the last character of the string are identical.

You are given a string S of length N (N >=2) . You have to make it

$Good$ string using the following operations.

$Operation 1$ : Remove a letter from the beginning of the string.
$Operation2$ : Remove a letter from the end of the string.

You can apply the $Operation1$ or $Operation2$ or both on the string S. Now your task is to find out the minimum number of operations to make the string S a $Good$ string.

Input:
The first line of the input will contain T , the number of testcases.
Next line will contain a string of a certain length. The string will consist of only lower case letters from 'a' to 'z'.

Output:
Print the minimum no of operations required. If impossible print "-1", without quotes .

Constraints:

$1 \le T \le 100$
$2 \le N \le 10^4$

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

For 1st test case:
The string is $abcda$ , we don't need to do any operations as the the string is already satisfying the criteria
For 2nd test case:
Here we have two options either remove the last b and make the string $abcdefghia$ , or remove the first a and make the original string $bcdefghiab$ , hence we need only 1 operation.
For 3rd test case:
No $Good$ string could be made
For 4th test case:
Remove the b from the beginning , and remove p , o , l from the end to make the string $acdefghipa$ (a $Good$ string ) hence total no of operations= $1+3=4$ .