Problem: consistency_ch1 (2021 quals)

**Note: This problem shares similarities with [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/A2). The solution to either chapter may help with solving the other, so please consider reading both first.**

Connie received a string \(S\) for her birthday, consisting entirely of uppercase letters (each between `"A"` and `"Z"`, inclusive).

However, Connie really only likes nice, *consistent* strings. She considers a string to be consistent if and only if all of its letters are the same.

Each second, Connie may choose one letter in \(S\) and replace it with a different letter. **If her chosen letter is a vowel, then she may replace it with any consonant of her choice. On the other hand, if her chosen letter is a consonant, then she may replace it with any vowel of her choice.** The \(5\) letters `"A"`, `"E"`, `"I"`, `"O"`, and `"U"` are considered vowels, while the remaining \(21\) letters of the alphabet are considered consonants. If a letter appears multiple times in \(S\), she may only replace a single occurrence per second.

Help her determine the minimum number of seconds required to change \(S\) into any consistent string. Note that \(S\) might already be consistent, in which case \(0\) seconds would be required.

# Constraints

\(1 \le T \le 45\)
\(1 \le |S| \le 100\)
`"A"` \(\le S_i \le\) `"Z"`

The sum of \(|S|\) across all test cases is at most \(4{,}500\).

# Input

Input begins with an integer \(T\), the number of birthdays Connie has had. For each birthday, there is a single line containing the string \(S\).

# Output

For the \(i\)th string, print a line containing *"Case #i: "* followed by the minimum number of seconds required to change \(S\) into any consistent string.

# Sample Explanation

In the first case, Connie could replace the second and third letters (`"B"` and `"C"`) each with `"A"`, yielding the string `"AAA"` in \(2\) seconds.

In the second case, `"F"` is already consistent.

In the third case, Connie could replace the first, third, and fifth letters (`"B"`, `"N"`, and `"N"`) each with `"A"`, yielding the string `"AAAAAA"` in \(3\) seconds.


Sample input:
6
ABC
F
BANANA
FBHC
FOXEN
CONSISTENCY


Sample output:
Case #1: 2
Case #2: 0
Case #3: 3
Case #4: 4
Case #5: 5
Case #6: 12


Solution: There are only \(26\) possible consistent strings which \(S\) might be changed into, with all characters in \(S\) ending up equal to some character \(x\) (`"A"` \(\le x \le\) `"Z"`). We'll consider each possible value of \(x\) and compute the total number of seconds required to change all characters in \(S\) into \(x\), with the minimum of those \(26\) possible totals being our final answer.

For each character \(x\), we'll need to consider each character \(c\) in \(S\) and compute the number of seconds required to change \(c\) into \(x\). If \(c = x\), then \(0\) seconds are required. If \(c\) is a vowel while \(x\) is a consonant (or vice versa), then \(1\) second is required. Otherwise (that is, \(c\) and \(x\) differ but are either both vowels or both consonants), \(2\) seconds are required.

[See David Harmeyer's solution video here](https://youtu.be/p5yPTHNUTlc).


Code: #include <algorithm>
#include <iostream>
using namespace std;

const int INF = 1e6;

bool is_vowel(char c) {
  return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}

string S;

int solve() {
  cin >> S;
  int ans = INF;
  for (char c1 = 'A'; c1 <= 'Z'; c1++) {
    int curr = 0;
    for (char c2 : S) {
      if (c1 != c2) {
        curr += is_vowel(c1) == is_vowel(c2) ? 2 : 1;
      }
    }
    ans = min(ans, curr);
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}