Problem Statement
Given a string, determine the maximum number of times the word "balloon" can be formed using the characters from the string. Each character in the string can be used only once.
Examples:
-
Example 1:
- Input: "balloonballoon"
- Expected Output: 2
- Justification: The word "balloon" can be formed twice from the given string.
-
Example 2:
- Input: "bbaall"
- Expected Output: 0
- Justification: The word "balloon" cannot be formed from the given string as we are missing the character 'o' twice.
-
Example 3:
- Input: "balloonballoooon"
- Expected Output: 2
- Justification: The word "balloon" can be formed twice, even though there are extra 'o' characters.
Constraints:
- 1 <= text.length <= 10<sup>4</sup>
textconsists of lower case English letters only.
Why this is a Hash Maps problem
| What the question says | The signal it matches |
|---|---|
| "the maximum number of times the word" balloon "can be formed using the characters from the string" | two inputs are compared as collections rather than sequences |
| "Each character in the string can be used only once" | supply is limited, so the counts on both sides decide the answer |
| counting each needed letter by scanning the whole string again | your first idea is a nested loop that recounts the same thing |
Counting the supply and dividing it by what one copy needs is the count and compare variant.
The closest alternative. The order of the letters never matters, which rules out string searching.
Two letters need care. The word balloon uses l and o twice each, so their supply must be halved before comparing. The answer is the smallest ratio across the needed letters. Forgetting the doubled letters is the usual mistake.
Solution
To solve this problem, you start by creating a hashmap to count the frequency of each letter in the given string. Since the word "balloon" contains specific letters with varying frequencies (like 'l' and 'o' appearing twice), you need to account for these in your hashmap. Once you have the frequency of each letter, the next step is to determine how many times you can form the word "balloon". This is done by finding the minimum number of times each letter in "balloon" appears in the hashmap. The limiting factor will be the letter with the minimum frequency ratio to its requirement in the word "balloon". This approach ensures a balance between utilizing the available letters and adhering to the letter composition of "balloon".
-
Character Frequency Count: Traverse the string and populate a hashmap with the frequency count of each character.
-
Determine Maximum Count: Check the hashmap to determine the maximum number of times the word "balloon" can be formed. For characters 'b', 'a', and 'n', their frequency in the hashmap directly gives the number of times they can be used. For 'l' and 'o', we need to divide their frequency by 2.
-
Result Calculation: The minimum value among the counts of 'b', 'a', 'l'/2, 'o'/2, and 'n' will give the maximum number of times the word "balloon" can be formed.
-
Return the Result: Return the calculated minimum value as the final result.
This approach is effective because it ensures that we account for the frequency of each character required to form the word "balloon". Using a hashmap allows for efficient storage and retrieval of character frequencies.
Count every character in "balloonballoooon": b:2, a:2, l:4, o:6, n:2.
1 of 7
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity: The algorithm traverses the string once to populate the hashmap, which is O(n), where n is the length of the string. The subsequent operations are constant time. Therefore, the overall time complexity is O(n).
Space Complexity: The space complexity is determined by the hashmap, which in the worst case will have an entry for each unique character in the string. However, since the English alphabet has a fixed number of characters, the space complexity is O(1).
.....
.....
.....