Max Word Formations
You are given two strings: text and word. Your task is to determine the maximum number of times the word can be formed using the characters available in text. Each character in text can be used at most once for each complete formation of the word. If the word cannot be formed even once, return 0.
[ "hello", "he" ]
Explanation. To form "he", we need one 'h' and one 'e'. The text "hello" provides one 'h' and one 'e'. Thus, "he" can be formed once. Remaining characters: "llo".
[ "abccba", "abc" ]
Explanation. The text "abccba" has two 'a's, two 'b's, and two 'c's. The word "abc" requires one 'a', one 'b', and one 'c'. We can form "abc" twice as we have enough of each character (2 'a's for 1 'a' needed, 2 'b's for 1 'b' needed, 2 'c's for 1 'c' needed. The minimum ratio is 2/1 = 2).
[ "abc", "abcd" ]
Explanation. The word "abcd" requires a 'd', which is not present in the text "abc". Therefore, the word cannot be formed at all.
[ "apple", "pap" ]
Explanation. The text "apple" contains one 'a' and two 'p's. The word "pap" requires one 'a' and two 'p's. We have exactly enough characters to form "pap" once.
[ "programmingisfun", "program" ]
Explanation. The text "programmingisfun" contains: p:1, r:2, o:1, g:1, a:1, m:1, i:1, s:1, f:1, u:1, n:1. The word "program" requires: p:1, r:1, o:1, g:1, a:1, m:1. All required characters are present at least once in the text, and there are no characters needed more times than available that would limit formation to less than 1.
[ "zzzzzz", "zzz" ]
Explanation. The text has six 'z's. The word "zzz" requires three 'z's. We can form the word 6 / 3 = 2 times.
[ "", "a" ]
Explanation. The text is empty, so no characters are available to form any word.
[ "banana", "ban" ]
Explanation. Text "banana": b:1, a:3, n:2. Word "ban": b:1, a:1, n:1. We can form "ban" once. Remaining characters: "ana".
[ "racecar", "car" ]
Explanation. Text "racecar": r:2, a:2, c:2, e:1. Word "car": c:1, a:1, r:1. We can form "car" twice (e.g., first 'c','a','r', then second 'c','a','r').
[ "cat", "dog" ]
Explanation. None of the characters 'd', 'o', 'g' are present in "cat".
Follow-up: How would your approach change if you were given an array of target words and needed to find the maximum *total* number of word formations across all target words, such that each character in `text` is used globally and only once?
- `1 <= text.length <= 10^5` - `1 <= word.length <= 100` - `text` and `word` consist of lowercase English letters.
- Views
- 8