The Product Name

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:

1
2
3
ready
stedy
zebra

We make the following “matrix of occurrences”:

1
2
3
4
5
6
a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1
0  0  0  0  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0
1  1  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  2  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  2  0

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:

1
2
3
4
5
y (because z occurs once)
z
z
z
z

Here is the idea in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int N; 
cin >> N;
vector<int> names(N);
copy_n(istream_iterator<string>(cin), N, begin(names));

array<array<int, 26>, 5> freq{};

for (auto& name : names)
{
    for (auto i=0; i<5; ++i)
    {
        freq[i][name[i]-'a']++;
    }
}

string res;
for (auto i=0; i<5; ++i)
{
    auto lastZero = min_element(rbegin(freq[i]), rend(freq[i]));
    res += 'a' + (distance(lastZero, rend(freq[i]))-1);
}

cout << res;

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)
comments powered by Disqus