1170. Compare Strings by Frequency of the Smallest Character #

Problem #

Let’s define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

Example 1:

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

Constraints:

• 1 <= queries.length <= 2000
• 1 <= words.length <= 2000
• 1 <= queries[i].length, words[i].length <= 10
• queries[i][j], words[i][j] are English lowercase letters.

Problem Summary #

Let’s define a function f(s), where the input parameter s is a non-empty string; this function counts the frequency of the smallest letter in s  (by lexicographical order).

For example, if s = “dcce”, then f(s) = 2, because the smallest letter is “c”, and it appears 2 times.

Now, given two string arrays, the query table queries and the vocabulary table words, return an integer array answer as the result, where each answer[i] is the number of words satisfying f(queries[i]) < f(W), and W is a word in the vocabulary table words.

Notes:

• 1 <= queries.length <= 2000
• 1 <= words.length <= 2000
• 1 <= queries[i].length, words[i].length <= 10
• queries[i][j], words[i][j] are all lowercase English letters.

Solution Approach #

• Given 2 arrays, queries and words, for each queries[i], count the number of words[j] in words[j] that satisfy the condition f(queries[i]) < f(words[j]). The definition of f(string) is the frequency of the lexicographically smallest letter in string.
• First, according to the problem statement, construct the f() function, compute the f() value for each words[j], and then sort them. Then compute the f() value of each queries[i] in order. For each f() value, perform binary search among the f() values of words[j] to find the index k of a value greater than it; n-k is the number of elements whose f() value is greater than that of queries[i]. Output them to the result array in order.

Code #

package leetcode

import "sort"

func numSmallerByFrequency(queries []string, words []string) []int {
	ws, res := make([]int, len(words)), make([]int, len(queries))
	for i, w := range words {
		ws[i] = countFunc(w)
	}
	sort.Ints(ws)
	for i, q := range queries {
		fq := countFunc(q)
		res[i] = len(words) - sort.Search(len(words), func(i int) bool { return fq < ws[i] })
	}
	return res
}

func countFunc(s string) int {
	count, i := [26]int{}, 0
	for _, b := range s {
		count[b-'a']++
	}
	for count[i] == 0 {
		i++
	}
	return count[i]
}