Top K N-gram Anagram Groups
Problem statement
You are given a piece of text text, an n-gram size n and a number k.
- Split
textinto words. An n-gram isnconsecutive words, written with single spaces. Take every n-gram, starting at every word position, so they overlap. - Put two n-grams in the same anagram group when they use exactly the same letters the same number of times, ignoring spaces. For example,
"listen to"and"silent to"are in one group, and so are"ab cd"and"cd ab". - A group's count is the number of n-gram positions that belong to it. A group's name is its alphabetically smallest member.
Return the names of the k groups with the highest counts, highest first. Groups with equal counts are ordered by name, alphabetically. If there are fewer than k groups, return all of them.
Function
topAnagramGroups(text: String, n: int, k: int) → List<String>Examples
Example 1
text = "god dog act cat dog god tac"n = 1k = 2return = ["dog","act"]With n = 1 every word is its own n-gram. god and dog use the same letters, so they form one group with 4 occurrences. act, cat and tac form a group with 3. Each group is shown by its alphabetically smallest member: "dog", then "act".
Example 2
text = "listen to me silent to me"n = 2k = 2return = ["listen to","to me"]The 2-grams are listen to, to me, me silent, silent to and to me. listen to and silent to use the same letters, so their group has 2 occurrences. to me also has 2, and me silent has 1. The two groups with 2 tie, so they are ordered by their names: "listen to" comes before "to me".
Example 3
text = "a b a"n = 3k = 5return = ["a b a"]There is only one 3-gram, a b a, so only one group exists. k = 5 is more than the number of groups, so every group is returned.
Constraints
1 <= text.length <= 2 * 10^4textis words of 1 to 10 lowercase English letters separated by single spaces, with no leading or trailing space.1 <= n <= 3, andnis at most the number of words.1 <= k <= 100