Compare Strings by Frequency of the Smallest Character

Problem Id: 1170 Difficulty: Medium


Intuition

Solution


class Solution:
    def w(self, word):
        c = set(word)
        return word.count(min(c))

    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        fwords = [self.w(word) for word in words]
        fwords.sort()
        fqueries = [self.w(word) for word in queries]
        ans = []
        for q in fqueries:
            if q < fwords[0]:
                ans.append(len(fwords))
                continue
            if q >= fwords[-1]:
                ans.append(0)
                continue
            i = 0
            j = len(fwords) - 1
            while j - i > 1:
                mid = (i + j) // 2
                if q < fwords[mid]:
                    j = mid
                else:
                    i = mid
            ans.append(len(fwords) - j)
        return ans