add one solution for 1170

fishercoder1534 · fishercoder1534 · commit ac140b81211b · 2019-11-26T07:37:27.000-08:00
diff --git a/README.md b/README.md
@@ -38,6 +38,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |1154|[Day of the Year](https://leetcode.com/problems/day-of-the-year/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1154.java) | O(1) | O(1) | |Easy||
 |1137|[N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1137.java) | O(n) | O(n) | |Easy||
 |1122|[Relative Sort Array](https://leetcode.com/problems/relative-sort-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1122.java) | O(n) | O(n) | |Easy||
+|1170|[Compare Strings by Frequency of the Smallest Character](https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1170.java) | | | |Easy||
 |1089|[Duplicate Zeros](https://leetcode.com/problems/duplicate-zeros/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1089.java) | O(n^2) | O(1) | |Easy||
 |1079|[Letter Tile Possibilities](https://leetcode.com/problems/letter-tile-possibilities/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1079.java) | O(1) | O(1) | |Medium||
 |1078|[Occurrences After Bigram](https://leetcode.com/problems/occurrences-after-bigram/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1078.java) | O(n) | O(1) | |Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1170.java b/src/main/java/com/fishercoder/solutions/_1170.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.Arrays;
+
 /**
  * 1170. Compare Strings by Frequency of the Smallest Character
  *
@@ -28,8 +30,55 @@
  * */
 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) {
-            return null;
+            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;
         }
     }
 }
diff --git a/src/test/java/com/fishercoder/_1170Test.java b/src/test/java/com/fishercoder/_1170Test.java
@@ -0,0 +1,33 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1170;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _1170Test {
+    private static _1170.Solution1 solution1;
+    private static String[] queries;
+    private static String[] words;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1170.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        queries = new String[]{"cbd"};
+        words = new String[]{"zaaaz"};
+        assertArrayEquals(new int[]{1}, solution1.numSmallerByFrequency(queries, words));
+    }
+
+    @Test
+    public void test2() {
+        queries = new String[]{"bbb", "cc"};
+        words = new String[]{"a", "aa", "aaa", "aaaa"};
+        assertArrayEquals(new int[]{1, 2}, solution1.numSmallerByFrequency(queries, words));
+    }
+
+}
