Task 9 - Letter set - solution


Task text

Ana is learning to build words from letters. Today she wants to build as many copies as possible of a word she has thought of, using the letters she has. Write a program that determines how many times the given word can be built from the letters of the given collection.

Input

The first line of standard input contains a string that represents the collection, and the second line a string that represents the word. Both strings consist only of lowercase letters of the English alphabet and their length is up to 50000 characters.

Output

Print one integer to standard output, the number of times the given word can be built.

Example 1

Input:
matematikaiprogramiranje
meta

Output:
2

Example 2

Input:
nekavelikakolekcijaslova
kea

Output:
3

Example 3

Input:
babanedanijevisesedapajenekogleda
deda

Output:
1

(The example collections are Serbian phrases, e.g. "matematikaiprogramiranje" means "mathematics and programming". Only the letters matter for the task.)


Idea of the solution

To build the word once, for every letter of the word there must be enough copies of that letter in the collection. That is why we first count how many times every letter appears in the collection, and how many times in the word.

If the letter c appears word[c] times in the word, and coll[c] times in the collection, then that letter "allows" at most

coll[c] / word[c] (integer division)

builds of the word. The word can be built as many times as the most limiting letter allows, so the result is the minimum of these quotients over all letters that appear in the word. If some letter of the word does not exist in the collection at all, the quotient is 0, so the result is 0 as well.

Letters that do not appear in the word (word[c] == 0) are skipped, because they do not limit the result, and division by zero must not happen.

Example: for the collection matematikaiprogramiranje and the word meta we have m: 3/1 = 3, e: 2/1 = 2, t: 2/1 = 2, a: 6/1 = 6. The smallest quotient is 2, so the answer is 2.


Solution 1 in C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int minq;
    string s, r;
    int coll[26] = {0};
    int word[26] = {0};

    cin >> s >> r;

    // Upper bound: the word cannot be built more times
    // than the total number of letters in the collection allows.
    minq = s.size() / r.size();

    for (char c1 : s)
    {
        int pos = c1 - 'a';
        coll[pos]++;
    }

    for (char c2 : r)
    {
        int pos1 = c2 - 'a';
        word[pos1]++;
    }

    for (int i = 0; i < 26; i++)
    {
        if (word[i] == 0)
        {
            continue;
        }

        if (word[i] != 0 && coll[i] == 0)
        {
            minq = 0;
            continue;
        }

        int t = coll[i] / word[i];

        if (t < minq)
        {
            minq = t;
        }
    }

    cout << minq << endl;

    return 0;
}

Explanation of solution 1

The program uses two arrays of 26 elements each, one counter for every letter from 'a' to 'z'. The expression c1 - 'a' turns a letter into an index: 'a' gives 0, 'b' gives 1 and so on. Then, for every letter of the word, the quotient coll[i] / word[i] is computed and the smallest one is remembered.

The starting value minq = s.size() / r.size() is interesting. A word of length m cannot be built more than n / m times from n letters, so this is a correct upper bound and the solution gives correct results.

Weaknesses of solution 1 and what should be fixed


Solution 2 in C++

#include <iostream>
#include <string>
#include <climits>    // for INT_MAX
#include <algorithm>  // for min

using namespace std;

int main()
{
    int minq = INT_MAX;
    string s, r;
    int coll[26] = {0};
    int word[26] = {0};

    // Reading the strings
    cin >> s >> r;

    // Counting the letters in the collection
    for (char c1 : s)
    {
        coll[c1 - 'a']++;
    }

    // Counting the letters in the word
    for (char c2 : r)
    {
        word[c2 - 'a']++;
    }

    // Finding the smallest number of times the word can be built
    for (int i = 0; i < 26; i++)
    {
        if (word[i] > 0)
        {
            if (coll[i] == 0)
            {
                minq = 0;  // A letter of the word is missing
                break;
            }
            minq = min(minq, coll[i] / word[i]);
        }
    }

    // Printing the result
    cout << minq << endl;

    return 0;
}

Fixes compared to the old version of solution 2

Explanation of the important parts of the program


Solution 3: counting with unordered_map

On the old page, solution 3 was a literal copy of solution 2, although the text below it described a solution with unordered_map. Here exactly that solution is shown, so that the description and the code match.

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
#include <algorithm>

using namespace std;

int main()
{
    string s, r;
    cin >> s >> r;

    // The key is a letter, and the value is the number of its occurrences.
    unordered_map<char, int> coll, word;

    for (char c : s)
    {
        coll[c]++;
    }

    for (char c : r)
    {
        word[c]++;
    }

    int minq = INT_MAX;

    // We go only through the letters that appear in the word.
    for (const auto& p : word)
    {
        char letter = p.first;
        int needed = p.second;

        auto it = coll.find(letter);
        int available = (it == coll.end()) ? 0 : it->second;

        minq = min(minq, available / needed);

        if (minq == 0)
        {
            break;  // A result better than 0 is not possible.
        }
    }

    cout << minq << endl;

    return 0;
}

Explanation of solution 3

Is solution 3 faster?

No. For this task, where the input contains only the 26 lowercase letters, an array of 26 elements (solutions 1 and 2) is simpler and somewhat faster than unordered_map, because accessing an array does not require computing a hash. The old claim that solution 3 is "optimized" is not true; it is more general, not faster. For competitions, solution 2 is the best choice.


Additional examples

Example 1

Input:
abcdeabcdeabcde
abc

Output:
3

The collection has 15 letters: the string abcde is repeated 3 times, so each of the letters a, b and c exists 3 times. The word uses each of them once, so the answer is 3.

Example 2

Input:
xyzxyzxyz
xyzz

Output:
1

The collection has 3 letters each of x, y and z. The word xyzz needs one x, one y and two letters z. The quotients are x: 3/1 = 3, y: 3/1 = 3, z: 3/2 = 1, so the answer is 1. (The old page wrongly said that the output is 2; a second build would need four letters z, but there are only three.)

Example 3

Input:
abcdefgh
ijk

Output:
0

The letters i, j and k do not exist in the collection, so the word cannot be built even once.

Example 4

Input:
aabbcc
abcabc

Output:
1

The collection has 2 letters each of a, b and c, and the word abcabc uses each of them twice, so it can be built exactly once.


Complexity of the solutions

Conclusion

The task shows the technique of counting occurrences (a histogram of letters) and finding the most limiting resource using the minimum of quotients. The same idea is used in letter games such as Scrabble, but also in every problem where as many identical products as possible are made from limited supplies. Pay special attention to integer division and to the case when some letter is missing completely.