AABBCCDD - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: tanminati
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given a string S.
You can modify it as follows:

  • Convert any uppercase letter to the corresponding lowercase letter.
    This can be done any number of times.
  • Convert all occurrences of some lowercase letter to another lowercase letter.
    This can be done only once.

Maximize the number of occurrences of any single lowercase letter in the string.

EXPLANATION:

We only care about maximizing the number of occurrences of a single lowercase letter.
Since our operations are to convert uppercase → lowercase and lowercase → other lowercase, uppercase letters are not particularly useful by themselves.

Thus, we may as well just convert every uppercase letter to lowercase first - this doesn’t worsen the answer.

Now, we have a string S that has only lowercase letters.
The only operation available to us is to convert all occurrences of some character to some other character; and we can only do this once.
Since the goal is to maximize the number of occurrences of any single lowercase letter, the optimal solution is as follows:

  • Let c_1 be the character with the highest number of occurrences in S.
  • Let c_2 be the character with the second-highest number of occurrences in S.
  • Convert all occurrences of c_2 into c_1, so that the number of occurrences of both will merge.

More formally, let \text{freq} be an array such that \text{freq}[a], \text{freq}[b], \ldots, \text{freq}[z] denote the frequencies of a, b, \ldots, z in the string S (after converting all uppercase characters to lowercase.)
The answer is then simply

\max(\text{freq}) + \text{second\_max}(\text{freq})

Finding the maximum and second maximum elements in an array can be done in a couple of different ways:

  1. Sort the array and look at the last two elements.
  2. Alternately, find the maximum element in linear time, delete (one instance of) this maximum from the array, and then just find the maximum element again.

TIME COMPLEXITY:

\mathcal{O}(N) to \mathcal{O}(N \log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input().lower() # convert string to all lowercase
    
    import string
    freqs = []
    for c in string.ascii_lowercase: # iterate a, b, c, ..., z
        freqs.append(s.count(c))
    
    freqs.sort(reverse=True) # sort frequencies in descending order
    print(freqs[0] + freqs[1])