NINJA2 - PATHETIC STRINGS

A string is said to be “PATHETIC” if all the characters in it are repeated the same number of times. You are given a string of length n, what is the minimum number of changes required to make a string “PATHETIC”. The string has only lower case letters and you can change any letter to any other letter.

Input Format

The first line contains an integer T, the number of test cases. This is followed by T test cases each containing 1 line: Each testcase consists of a string composed of lowercase letters.

Output Format

For each testcase, print in a new line the minimum number of changes required.

Constraints

1 ≤ T ≤ 1370

1 ≤ n ≤ 1991

Sample

Input:
2
bbaccaaa
ccaacb

Output:
2
1

Added by:mombassa
Date:2016-02-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2020-08-01 01:03:26
Bruce force -- Hint: what's the possible # of repetitions?
2018-10-05 12:13:25 :D
Some hints:

Number of different characters that appear at all in the string can be changed. Example:
TestCase:
1
aaabbc
Result:
1 (change 'c' to 'b')

There can be only one letter in the input/output. Example:
1
aaaab
Result:
1 (change 'b' to 'a')

You should avoid ad hoc solution and find a simple, but general algorithm. Think how many different letters can appear in a "pathetic" string?

2016-07-12 11:35:09
Frustrated by this.... WA at 11 case... Someone Help
2016-07-12 09:01:53 Dushyant Singh
What will be the answer for
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa

(length=29)

Last edit: 2016-07-12 09:02:34
2016-04-03 18:44:54
what will be output for "aaaaaaab" 1 or 3
pathetic string can be of single type character??
plz help mombassa

Last edit: 2016-04-04 12:52:33
2016-03-24 16:35:25 GUDDU
Any possible hints ?
2016-03-13 15:40:45 mehmetin
"You can change any letter to any other letter". That sentence in the description is very important...

Last edit: 2016-03-13 17:00:47
2016-03-02 06:14:46
@lalit_nit 3 might be the output.
cadeb
2016-02-22 13:41:12
Give output for "cccbb" please...
Edit: @gurugs You should solve it frst :p ....

Last edit: 2016-03-02 21:42:32
2016-02-20 19:42:27 Ankit
Stuck at wrong answer now. Some weird boundary condition ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.