MINSTR - Editorial

animesh_f · December 17, 2017, 3:17am

PROBLEM LINK:

PROBLEM

You are given an array A of atmost 10^5 strings where each string is from the set {“a”, “aa”, “ab”, “b”, “ba”, “bb”}. Fix a permutation P of {1, 2, \cdots, n} and consider the string A_{P_1} + A_{P_2} + \cdots + A_{P_n} formed by concatenation of the mini strings. Now, replace each contiguous block of “a” and “b” with a single “a” and “b” and compute the length of this reduced string. Let’s call this length L.

The task is to find a permutation that minimizes L, and print the minimum value of L.

EXPLANATION

The solution uses a simple greedy algorithm. Note that minimizing the total length is the same as maximizing the
total reduction. Here is a step-by-step description of the algorithm:

First, we normalize all the a and aa strings to one a. Similarly, normalize all b and bb strings to one b.
Note that the only other reduction in length we can get is if we pair ab strings with ba strings. Assume that
the freq(ab) \ge freq(ba). In this case we can interleave them greedily like ab + ba + ab + \cdots until we
run out of ba strings. Then we finish it with the remaining ab strings. We can apply a similar argument for the case where freq(ab) < freq(ba).
Finally, we can merge an existing a with the string we’ve made till now. Similarly, we can merge an existing b.

Overall, assume we’ve computed the number of a, b, ab and ba strings we have. Then the following pseudocode finds the optimal solution:

a = min(a, 1); // Normalize "a" and "aa"
b = min(b, 1); // Normalize "b" and "bb"
if (ab == 0 && ba == 0) { // Edge case where we can't reduce more
    print(a + b);
} else if (ab == ba) { // When the counts are equal we will need one extra
    print(ab + ab + 1);
} else {
    print(max(ab, ba) * 2);
}

Clearly, this solution is O(n).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.