LeetCode 1170. Compare Strings by Frequency of the Smallest Character Solution in Java, C++, Python & More | Explanation + Code

Description

Let the function f(s) be the frequency of the lexicographically smallest character in a non-empty string s. For example, if s = "dcce" then f(s) = 2 because the lexicographically smallest character is 'c', which has a frequency of 2.

You are given an array of strings words and another array of query strings queries. For each query queries[i], count the number of words in words such that f(queries[i]) < f(W) for each W in words.

Return an integer array answer, where each answer[i] is the answer to the ith query.

 

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] consist of lowercase English letters.

Solutions

Solution 1: Sorting + Binary Search

First, according to the problem description, we implement a function f(s), which returns the frequency of the smallest letter in the string s in lexicographical order.

Next, we calculate f(w) for each string w in words, sort them, and store them in an array nums.

Then, we traverse each string q in queries, and binary search in nums for the first position i that is greater than f(q). Then, the elements at index i and after in nums all satisfy f(q) < f(W), so the answer to the current query is n - i.

The time complexity is O((n + q) × M), and the space complexity is O(n). Here, n and q are the lengths of the arrays words and queries respectively, and M is the maximum length of the strings.

PythonJavaC++GoTypeScript

class Solution: def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]: def f(s: str) -> int: cnt = Counter(s) return next(cnt[c] for c in ascii_lowercase if cnt[c]) n = len(words) nums = sorted(f(w) for w in words) return [n - bisect_right(nums, f(q)) for q in queries](code-box)

class Solution { public int[] numSmallerByFrequency(String[] queries, String[] words) { int n = words.length; int[] nums = new int[n]; for (int i = 0; i < n; ++i) { nums[i] = f(words[i]); } Arrays.sort(nums); int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int x = f(queries[i]); int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] > x) { r = mid; } else { l = mid + 1; } } ans[i] = n - l; } return ans; } private int f(String s) { int[] cnt = new int[26]; for (int i = 0; i < s.length(); ++i) { ++cnt[s.charAt(i) - 'a']; } for (int x : cnt) { if (x > 0) { return x; } } return 0; } }(code-box)

class Solution { public: vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) { auto f = [](string s) { int cnt[26] = {0}; for (char c : s) { cnt[c - 'a']++; } for (int x : cnt) { if (x) { return x; } } return 0; }; int n = words.size(); int nums[n]; for (int i = 0; i < n; i++) { nums[i] = f(words[i]); } sort(nums, nums + n); vector<int> ans; for (auto& q : queries) { int x = f(q); ans.push_back(n - (upper_bound(nums, nums + n, x) - nums)); } return ans; } };(code-box)

func numSmallerByFrequency(queries []string, words []string) (ans []int) { f := func(s string) int { cnt := [26]int{} for _, c := range s { cnt[c-'a']++ } for _, x := range cnt { if x > 0 { return x } } return 0 } n := len(words) nums := make([]int, n) for i, w := range words { nums[i] = f(w) } sort.Ints(nums) for _, q := range queries { x := f(q) ans = append(ans, n-sort.SearchInts(nums, x+1)) } return }(code-box)

function numSmallerByFrequency(queries: string[], words: string[]): number[] { const f = (s: string): number => { const cnt = new Array(26).fill(0); for (const c of s) { cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++; } return cnt.find(x => x > 0); }; const nums = words.map(f).sort((a, b) => a - b); const ans: number[] = []; for (const q of queries) { const x = f(q); let l = 0, r = nums.length; while (l < r) { const mid = (l + r) >> 1; if (nums[mid] > x) { r = mid; } else { l = mid + 1; } } ans.push(nums.length - l); } return ans; }(code-box)