package com.fishercoder.solutions;

import java.util.Arrays;

/**
 * 1170. 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.
 * */
public class _1170 {
    public static class Solution1 {
        /**
         * Use simple iteration when finding counts
         * Time: O(n^m) where m is the size of queries and n is the size of words
         * Space: O(max(m, n) where m is the size of queries and n is the size of words)
         * */
        public int[] numSmallerByFrequency(String[] queries, String[] words) {
            int[] queriesMinFrequecies = new int[queries.length];
            for (int i = 0; i < queries.length; i++) {
                queriesMinFrequecies[i] = computeLowestFrequency(queries[i]);
            }

            int[] wordsMinFrequecies = new int[words.length];
            for (int i = 0; i < words.length; i++) {
                wordsMinFrequecies[i] = computeLowestFrequency(words[i]);
            }
            Arrays.sort(wordsMinFrequecies);

            int[] result = new int[queries.length];
            for (int i = 0; i < result.length; i++) {
                result[i] = search(wordsMinFrequecies, queriesMinFrequecies[i]);
            }
            return result;
        }

        private int search(int[] nums, int target) {
            int count = 0;
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] > target) {
                    count++;
                } else {
                    break;
                }
            }
            return count;
        }

        private int computeLowestFrequency(String string) {
            char[] str = string.toCharArray();
            Arrays.sort(str);
            String sortedString = new String(str);
            int frequency = 1;
            for (int i = 1; i < sortedString.length(); i++) {
                if (sortedString.charAt(i) == sortedString.charAt(0)) {
                    frequency++;
                } else {
                    break;
                }
            }
            return frequency;
        }
    }

    public static class Solution2 {
        /**
         * Use binary search when finding counts
         * Time: O(n^logn) where m is the size of queries and n is the size of words
         * Space: O(max(m, n) where m is the size of queries and n is the size of words)
         * */
        public int[] numSmallerByFrequency(String[] queries, String[] words) {
            int[] queriesMinFrequecies = new int[queries.length];
            for (int i = 0; i < queries.length; i++) {
                queriesMinFrequecies[i] = computeLowestFrequency(queries[i]);
            }

            int[] wordsMinFrequecies = new int[words.length];
            for (int i = 0; i < words.length; i++) {
                wordsMinFrequecies[i] = computeLowestFrequency(words[i]);
            }
            Arrays.sort(wordsMinFrequecies);

            int[] result = new int[queries.length];
            for (int i = 0; i < result.length; i++) {
                result[i] = binarySearch(wordsMinFrequecies, queriesMinFrequecies[i]);
            }
            return result;
        }

        private int binarySearch(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] <= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return nums.length - left;
        }

        private int computeLowestFrequency(String string) {
            char[] str = string.toCharArray();
            Arrays.sort(str);
            String sortedString = new String(str);
            int frequency = 1;
            for (int i = 1; i < sortedString.length(); i++) {
                if (sortedString.charAt(i) == sortedString.charAt(0)) {
                    frequency++;
                } else {
                    break;
                }
            }
            return frequency;
        }
    }
}

@@ -59,1101 +59,8 @@
 s;%0A%0A
-/**%0A * 1170. Compare Strings by Frequency of the Smallest Character%0A *%0A * Let's define a function f(s) over a non-empty string s,%0A * which calculates the frequency of the smallest character in s.%0A * For example, if s = %22dcce%22 then f(s) = 2 because the smallest character is %22c%22 and its frequency is 2.%0A * Now, given string arrays queries and words,%0A * return an integer array answer,%0A * where each answer%5Bi%5D is the number of words such that f(queries%5Bi%5D) %3C f(W), where W is a word in words.%0A *%0A * Example 1:%0A * Input: queries = %5B%22cbd%22%5D, words = %5B%22zaaaz%22%5D%0A * Output: %5B1%5D%0A * Explanation: On the first query we have f(%22cbd%22) = 1, f(%22zaaaz%22) = 3 so f(%22cbd%22) %3C f(%22zaaaz%22).%0A *%0A * Example 2:%0A * Input: queries = %5B%22bbb%22,%22cc%22%5D, words = %5B%22a%22,%22aa%22,%22aaa%22,%22aaaa%22%5D%0A * Output: %5B1,2%5D%0A * Explanation: On the first query only f(%22bbb%22) %3C f(%22aaaa%22). On the second query both f(%22aaa%22) and f(%22aaaa%22) are both %3E f(%22cc%22).%0A *%0A * Constraints:%0A * 1 %3C= queries.length %3C= 2000%0A * 1 %3C= words.length %3C= 2000%0A * 1 %3C= queries%5Bi%5D.length, words%5Bi%5D.length %3C= 10%0A * queries%5Bi%5D%5Bj%5D, words%5Bi%5D%5Bj%5D are English lowercase letters.%0A * */%0A
 publ
@@ -347,34 +347,32 @@
  words)%0A        
- *
  */%0A        publ
@@ -2263,18 +2263,16 @@
         
- *
  */%0A    

refactor 1170