Clean the string

4.3

9 votes
String Searching, Greedy Algorithms, Algorithms, String, String Algorithms
Problem

El has a string S consisting of '0', '1' and '2' as only characters. El is a sorted person, so he does not like randomness, so when he looks at the string and finds that characters in string are in random order, he becomes frustrated. He wants to clean up the string, i.e, he wants all same characters in the string to appear together. In one move El can swap any two characters in the string, i.e, he can select index i, j then swap Si and Sj. Find the minimum number of moves required to clean the string.

Input Format

  • First line contains an integer T, which denotes the number of test cases.
  • Each line of the test case contains a  string S consisting of '0', '1' and '2' as only characters.

Output Format

For each test case print only one integer - the minimum no. of moves required.

Constraint

1T1041|S|2105Sum of length of strings for all test case does not exceed 2105

 

Sample Input
4
000
2010112
1011210
2120201
Sample Output
0
2
1
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • In the first test case all characters are 0, so no swaps are required. 
  • In the second case, we require two swaps:
    • Swap S1 and S6 after which the string becomes: 2210110
    • Swap S2 and S6 after which the string becomes: 2200111 (All same characters are together).
Editor Image

?