Compare Strings by Frequency of the Smallest Character

Kind of a weird problem, but anywho, here it is: https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/

Approach is simple:
  • Build a frequency function (linear in the length of the input string)
  • Build the frequency arrays for both queries and words
  • Sort frequency words
  • At this point you could do a Binary Search (ideal) or use a search for the first instance where the frequency query is larger than the frequency word, and halt (that's what I did)
Worked reasonably well. Code is below, cheers, ACC.


public class Solution
{
    public int[] NumSmallerByFrequency(string[] queries, string[] words)
    {
        int[] queriesNumbers = new int[queries.Length];
        int[] wordsNumbers = new int[words.Length];

        for (int i = 0; i < queries.Length; i++)
        {
            queriesNumbers[i] = Frequency(queries[i]);
        }
        for (int i = 0; i < words.Length; i++)
        {
            wordsNumbers[i] = Frequency(words[i]);
        }

        Array.Sort(wordsNumbers);

        int[] result = new int[queriesNumbers.Length];
        for (int i = 0; i < queriesNumbers.Length; i++)
        {
            result[i] = 0;
            for (int j = wordsNumbers.Length - 1; j >= 0 && wordsNumbers[j] > queriesNumbers[i]; j--)
            {
                result[i]++;
            }
        }

        return result;
    }
    private int Frequency(string word)
    {
        char[] letters = new char[26];

        int minIndex = 27;
        int retValue = 0;
        for (int i = 0; i < word.Length; i++)
        {
            letters[word[i] - 'a']++;
            if (word[i] - 'a' <= minIndex)
            {
                minIndex = word[i] - 'a';
                retValue = letters[minIndex];
            }
        }

        return retValue;
    }
}

Comments

  1. I was solving this as part of the contest, so tried to be brief :)

    import bisect

    class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
    def f(word: str) -> int:
    word = sorted(word)
    return bisect.bisect_right(word, word[0])

    word_fs = sorted(f(word) for word in words)
    return [
    len(words) - bisect.bisect_right(word_fs, f(query)) for query in queries
    ]

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons