K Most Frequent Strings

Identify the N most frequent items in a collection, then return them in descending order of frequency. This is a common pattern for data analysis, search algorithms, and recommendation systems.

heaphash mapfrequencysortingdata structures

Problem Statement

Given a list of strings and an integer N, find the N most frequently occurring strings in the list. Return these strings in a list, sorted by their frequency from highest to lowest. If two strings have the same frequency, sort them alphabetically (lexicographically). Assume N is always less than or equal to the number of unique strings in the input list.

Example 1

Input: strings = ["apple", "banana", "apple", "orange", "banana", "apple", "kiwi"], N = 2

Output: ["apple", "banana"]

"apple" appears 3 times, "banana" appears 2 times, "orange" and "kiwi" appear once. The top 2 most frequent are "apple" and "banana". Since apple appears more, it will appear first.

Example 2

Input: strings = ["red", "blue", "green", "red", "blue", "red"], N = 3

Output: ["red", "blue", "green"]

"red" appears 3 times, "blue" appears 2 times, and "green" appears once. All strings are returned since N is 3 and there are 3 unique strings.

Constraints

-1 <= length of the input string list <= 10000
-1 <= N <= number of unique strings in the input list
-The strings will only contain lowercase letters.
-1 <= length of each string <= 20

Brute Force Approach

Imagine you're manually counting votes in an election. The brute force approach is like going through each ballot, counting how many times each name appears, then sorting the candidates by the number of votes they received. This involves comparing each string with every other string to count frequencies and then sorting all the strings. This has a time complexity of O(n^2) or O(n log n) depending on the sorting algorithm.

TimeO(n^2) or O(n log n)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem