See the original problem on HackerRank.
Solutions
Basically, each character \(out_i\) of the output string \(out\) occurs the least number of times at index \(i\) among all the input strings.
We can count the occurrences of each letter of the alphabet (26) for each position of the input strings. Since all the strings have \(5\) characters, we have \(5\) frequency tables.
Thus, we use constant additional storage - for instance, an array containing 5 arrays of 26 integers.
Roughly speaking, the first array contains the occurrences of each letter in the first column of the matrix formed by the input strings, the second array is for the second column, and so on.
For example, consider these input strings:
|
|
We make the following “matrix of occurrences”:
|
|
The first row states that r
, s
, and z
occurs once. Indeed, ready
starts with r
, steady
with s
and zebra
with z
.
In the second part of the solution, for each row we simply choose the last smallest element - that is the letter occurring the least number of times, starting from backwards.
We have to choose the “last” one because the distance will be maximal.
In the example above we choose:
|
|
Here is the idea in C++:
|
|
As you see, in C++ we can express iterating backwards with reverse iterators. We just use min_element
that returns the iterator to the element with the (first - meaning that if another minimum is found, the iterator is not updated) smallest value. Since we iterate backwards, the result is the “last” smallest element.
The complexity of the solution is linear (to fill up the frequency matrix) and the additional storage used is constant.
Possible problem perturbations:
- handle strings of any size (not only 5)
- handle strings of bigger alphabets (not only lower case letters)