Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?

Question

The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum number of strings that satisfies the condition. But I don`t believe it is ok, because for large numbers of strings the exponential nature of bkt (2^n subsets) will severely affect the time of execution.

Any other ways to find the maximum number of strings from the given list of strings, so that if you concatenate them the property is satisfied, would be welcomed.

Answer 1

Consider that dominant letter. Suppose it is $A$. Now the question is to find the maximum number of strings in which $A$s are the majority. So it is a duel between $A$s and all other letters.

A good string should have lots of $A$s. In fact, since it is a duel in cardinality, the most advantageous string should be the string in which the difference between the number of $A$s and the number of other letters are the greatest.

Can you see the greedy strategy?

---

The algorithm will run in $O(n+26k)$ time, where $n$ is the total length of all strings and $k$ is the number of strings, assuming all strings are made of uppercase English letters.