1170.Compare Strings by Frequency of the Smallest Character

Tags: Easy String Array

Links: https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/

---

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.

---

class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = queries.size(), n = words.size();
        vector<int> res(m);
        vector<int> q(m), w(n);
        //计算在queries里的最小字符的频率
        for (int i = 0; i < m; ++i) {
            char tmp = 'z' + 1;
            int cnt = 0;
            for (int j = 0; j < queries[i].size(); ++j) {
                if (queries[i][j] < tmp) {
                    tmp = queries[i][j];
                    cnt = 1;
                }
                else if (queries[i][j] == tmp) ++cnt;
            }
            q[i] = cnt;
        }
        //计算在words里最小字符的频率
        for (int i = 0; i < n; ++i) {
            char tmp = 'z' + 1;
            int cnt = 0;
            for (int j = 0; j < words[i].size(); ++j) {
                if (words[i][j] < tmp) {
                    tmp = words[i][j];
                    cnt = 1;
                }
                else if (words[i][j] == tmp) ++cnt;
            }
            w[i] = cnt;
        }
        //对w数组排序，利用二分查找优化
        sort(w.begin(), w.end());
        for (int i = 0; i < m; ++i) {
            res[i] = n - (upper_bound(w.begin(), w.end(), q[i]) - w.begin());
        }

        return res;
    }
};

每个字符串长度不超过10，统计queries的频率为$O(10m)$，统计words频率时间复杂度为$O(10n)$，对和words等长的数组排序$O(n\log n)$，查找时的$m \log n$，所以时间复杂度是$\max(n \log n, m \log n)$。

---

方法二：充分利用每个字符串长度不超过10这一条件，这也就意味着在words里面的对于每个单词，最小字符出现的频率肯定不超过10，所以就可以开一个长度为12的数组（便于去赋值，后续用作累加和来求值），去记录对应频率的单词的个数。然后计算大于某个频率的个数的时候，只需要从后往前累加即可。

class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = queries.size(), n = words.size();
        vector<int> res(m);
        vector<int> freq(12);
        //统计在words里面的每个单词最小字符出现的频率
        for (int i = 0; i < n; ++i) ++freq[getFreq(words[i])];
        //累计求和，freq[i]表示频率大于等于i的频率个数
        for (int i = 10; i >= 1; --i) freq[i] += freq[i + 1];
        //输出结果
        for (int i = 0; i < m; ++i) res[i] = freq[getFreq(queries[i]) + 1];

        return res;        
    }

    int getFreq(const string & s)
    {
        char tmp = 'z' + 1;
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] < tmp) {
                tmp = s[i];
                cnt = 1;
            }
            else if (s[i] == tmp) ++cnt;
        }
        return cnt;
    }
};

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Compare Strings by Frequency of the Smallest Character.
Memory Usage: 10.9 MB, less than 100.00% of C++ online submissions for Compare Strings by Frequency of the Smallest Character.

方法是后缀和