String Reverse solution codechef – Chef has a string SS consisting only of English lowercase letters (a – z). However, Hitesh does not like it and wants it to be reversed.

Hitesh wonders what is the minimum number of operations required to reverse the string SS using the following operation:

• Select any ii such that 1≤i≤|S|1≤i≤|S| and remove SiSi from its original position and append it to the end of the string (i.e. shift any character to the end of the string).

String Reverse solution codechef

For e.g. if S=S= abcde and we apply operation on i=2i=2, then SS becomes acdeb.

Help Hitesh find the minimum number of operations required to reverse SS.

It is guaranteed that it is possible to reverse the string in a finite number of operations.

Input Format

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• Each test case consists of a single line containing the string S.

Output Format

For each test case, output the minimum number of operations required to reverse the string SS.

String Reverse solution codechef

• 1≤T≤1031≤T≤103
• 1≤|S|≤1051≤|S|≤105
• Sum of |S||S| over all testcases does not exceed 2⋅1052⋅105.

Sample Input 1 

2
abdeba
codechef

Sample Output 1 

3
7

String Reverse solution codechef

• Test case-1: Following steps can be performed:

1. abdeba→abebadabdeba→abebad
2. abebad→abeadbabebad→abeadb
3. abeadb→abedbaabeadb→abedba

• Test case-2: following steps can be performed:

1. codechef→codechfecodechef→codechfe
2. codechfe→codecfehcodechfe→codecfeh
3. codecfeh→codefehccodecfeh→codefehc
4. codefehc→codfehcecodefehc→codfehce
5. codfehce→cofehcedcodfehce→cofehced
6. cofehced→cfehcedocofehced→cfehcedo