Formatted question description: https://leetcode.ca/all/1170.html

1170. Compare Strings by Frequency of the Smallest Character (Easy)

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.

Related Topics:
Array, String

Solution 1.

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int queriesLength = queries.length, wordsLength = words.length;
        int[] queriesFrequency = new int[queriesLength];
        int[] wordsFrequency = new int[wordsLength];
        for (int i = 0; i < queriesLength; i++)
            queriesFrequency[i] = frequency(queries[i]);
        for (int i = 0; i < wordsLength; i++)
            wordsFrequency[i] = frequency(words[i]);
        int[] nums = new int[queriesLength];
        for (int i = 0; i < queriesLength; i++) {
            int queryFrequency = queriesFrequency[i];
            for (int j = 0; j < wordsLength; j++) {
                int wordFrequency = wordsFrequency[j];
                if (queryFrequency < wordFrequency)
                    nums[i]++;
            }
        }
        return nums;
    }

    public int frequency(String str) {
        int[] count = new int[26];
        char[] array = str.toCharArray();
        for (char c : array)
            count[c - 'a']++;
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0)
                return count[i];
        }
        return 0;
    }
}

############

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int n = words.length;
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = f(words[i]);
        }
        Arrays.sort(arr);
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int x = f(queries[i]);
            ans[i] = n - search(arr, x);
        }
        return ans;
    }

    private int search(int[] arr, int x) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    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 v : cnt) {
            if (v > 0) {
                return v;
            }
        }
        return 0;
    }
}

// OJ: https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/
// Time: O(W*Q)
// Space: O(W)
class Solution {
    int frequency(string &s) {
        int ch = 'z', cnt = 0;
        for (char c : s) {
            if (c < ch) {
                cnt = 1;
                ch = c;
            } else if (c == ch) ++cnt;
        }
        return cnt;
    }
public:
    vector<int> numSmallerByFrequency(vector<string>& Q, vector<string>& W) {
        vector<int> F(W.size()), ans;
        for (int i = 0; i < W.size(); ++i) F[i] = frequency(W[i]);
        for (auto &s : Q) {
            int cnt = 0, f = frequency(s);
            for (int i = 0; i < W.size(); ++i) cnt += F[i] > f;
            ans.push_back(cnt);
        }
        return ans;
    }
};

class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        def f(s):
            cnt = Counter(s)
            for c in ascii_lowercase:
                if cnt[c]:
                    return cnt[c]

        arr = [f(s) for s in words]
        arr.sort()
        n = len(arr)
        return [n - bisect_right(arr, f(q)) for q in queries]

############

# 1170. Compare Strings by Frequency of the Smallest Character
# https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/

class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        res, res1, res2 = [], [], []
        
        def f(word):
            count = [0] * 26
            for w in word:
                count[ord(w) - ord('a')] += 1

            for c in count:
                if c != 0: return c
            
            return -1
            
        for word in queries:
            res1.append(f(word))
        
        for word in words:
            res2.append(f(word))
        
        for x in res1:
            count = 0
            for y in res2:
                if y > x:
                    count += 1
            
            res.append(count)
        
        return res
        
        
            

func numSmallerByFrequency(queries []string, words []string) (ans []int) {
	f := func(s string) int {
		cnt := [26]int{}
		for _, c := range s {
			cnt[c-'a']++
		}
		for _, v := range cnt {
			if v > 0 {
				return v
			}
		}
		return 0
	}
	arr := []int{}
	for _, s := range words {
		arr = append(arr, f(s))
	}
	sort.Ints(arr)
	n := len(arr)
	for _, q := range queries {
		x := f(q)
		ans = append(ans, n-sort.Search(n, func(i int) bool { return arr[i] > x }))
	}
	return
}

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)]++;
        }
        for (const x of cnt) {
            if (x) {
                return x;
            }
        }
        return 0;
    };
    const nums: number[] = [];
    for (const w of words) {
        nums.push(f(w));
    }
    nums.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;
}

1170 - Compare Strings by Frequency of the Smallest Character

1170. Compare Strings by Frequency of the Smallest Character (Easy)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1170. Compare Strings by Frequency of the Smallest Character (Easy)

Solution 1.

All Problems

All Solutions