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
- The solution is correct and fast enough, but there are several things that should be fixed for style and safety.
- When a letter that is not in the collection is found, the answer is certainly 0, so
breakshould be used instead ofcontinue. The loop then has no reason to continue. - The condition
word[i] != 0in the secondifis unnecessary, because the caseword[i] == 0has already been skipped. - If the word were empty,
s.size() / r.size()would be a division by zero. According to the task this does not happen, but in general it should be checked. - The original version was missing
#include <string>. Some compilers include it through<iostream>, but you should not count on that; it has been added here.
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
- The old version had
using namespacestd;(without a space). Such code does not compile; the correct form isusing namespace std;. #include <algorithm>was added for the functionmin, and#include <string>for the typestring.
Explanation of the important parts of the program
int minq = INT_MAX;sets the starting minimum to the largest possible value of typeint, so the first computed quotient will certainly replace it.string s, r;store the collection and the word, and the arrayscollandwordstore the number of occurrences of every letter.cin >> s >> r;reads both strings. Since the strings do not contain spaces,cin >>is enough.coll[c1 - 'a']++increases the counter of the letterc1.- In the last loop, for every letter that appears in the word,
coll[i] / word[i]is computed, andminkeeps the smallest value. If the letter is not in the collection, 0 is set immediately and the loop is stopped withbreak. - Since the word contains at least one letter, the
if (word[i] > 0)branch is entered at least once, soINT_MAXis never printed.
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
unordered_map<char, int>stores pairs letter – number of occurrences, so there is no need to compute the indexc - 'a'.- The loop goes only through the letters that exist in the word, so the check
word[i] > 0is not needed. coll.find(letter)checks whether the letter exists in the collection. For a letter that is not there, the available number is 0, so the result is 0 as well.- This solution also works when the input contains uppercase letters, digits or other characters, while arrays of 26 elements would get an index out of range in that case.
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
- All three solutions have time complexity O(n + m), where
nis the length of the collection andmis the length of the word. Every string is traversed once, and the final loop has at most 26 steps. - The additional memory is O(1): two arrays of 26 numbers or two maps with at most 26 keys.
- For the largest input of 50000 characters, all three solutions run in a few milliseconds, so they pass all tests in time.
- The result cannot be greater than 50000, so the type
intis enough.
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.
| Previous |< Qualifications for district competitions |
Next Municipal competitions (SR) >| |
