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

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 1i|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).

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.

Constraints

  • 1T1031≤T≤103
  • 1|S|1051≤|S|≤105
  • Sum of |S||S| over all testcases does not exceed 21052⋅105.

Sample Input 1 

2
abdeba
codechef

Sample Output 1 

3
7

Explanation

  • Test case-1: Following steps can be performed:
  1. abdebaabebadabdeba→abebad
  2. abebadabeadbabebad→abeadb
  3. abeadbabedbaabeadb→abedba
  • Test case-2: following steps can be performed:
  1. codechefcodechfecodechef→codechfe
  2. codechfecodecfehcodechfe→codecfeh
  3. codecfehcodefehccodecfeh→codefehc
  4. codefehccodfehcecodefehc→codfehce
  5. codfehcecofehcedcodfehce→cofehced
  6. cofehcedcfehcedocofehced→cfehcedo
  7. cfehcedofehcedoc
  8. For Solution

    Click Here!

Leave a Comment

Your email address will not be published.