add a solution for 451

fishercoder1534 · fishercoder1534 · commit c850dc990ced · 2021-10-22T07:05:44.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_451.java b/src/main/java/com/fishercoder/solutions/_451.java
@@ -5,6 +5,7 @@
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.TreeMap;
 
 public class _451 {
 
@@ -25,4 +26,31 @@ public String frequencySort(String s) {
             return stringBuilder.toString();
         }
     }
+
+    public static class Solution2 {
+        public String frequencySort(String s) {
+            Map<Character, Integer> map = new HashMap<>();
+            for (char c : s.toCharArray()) {
+                map.put(c, map.getOrDefault(c, 0) + 1);
+            }
+            TreeMap<Integer, List<Character>> reverseMap = new TreeMap<>(Collections.reverseOrder());
+            for (char c : map.keySet()) {
+                int freq = map.get(c);
+                if (!reverseMap.containsKey(freq)) {
+                    reverseMap.put(freq, new ArrayList<>());
+                }
+                reverseMap.get(freq).add(c);
+            }
+            StringBuilder sb = new StringBuilder();
+            for (int freq : reverseMap.keySet()) {
+                List<Character> list = reverseMap.get(freq);
+                for (char c : list) {
+                    for (int i = 0; i < freq; i++) {
+                        sb.append(c);
+                    }
+                }
+            }
+            return sb.toString();
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_451Test.java b/src/test/java/com/fishercoder/_451Test.java
@@ -1,53 +1,44 @@
 package com.fishercoder;
 
 import com.fishercoder.solutions._451;
-import org.junit.Before;
 import org.junit.BeforeClass;
 import org.junit.Test;
 
 import static junit.framework.Assert.assertEquals;
 
-/**
- * Created by fishercoder on 1/15/17.
- */
 public class _451Test {
     private static _451.Solution1 solution1;
+    private static _451.Solution2 solution2;
     private static String expected;
-    private static String actual;
     private static String input;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _451.Solution1();
-    }
-
-    @Before
-    public void setupForEachTest() {
-        expected = "";
-        actual = "";
+        solution2 = new _451.Solution2();
     }
 
     @Test
     public void test1() {
         input = "tree";
         expected = "eert";
-        actual = solution1.frequencySort(input);
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.frequencySort(input));
+        assertEquals(expected, solution2.frequencySort(input));
     }
 
     @Test
     public void test2() {
         input = "cccaaa";
         expected = "aaaccc";
-        actual = solution1.frequencySort(input);
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.frequencySort(input));
+        assertEquals(expected, solution2.frequencySort(input));
     }
 
     @Test
     public void test3() {
         input = "Aabb";
         expected = "bbAa";
-        actual = solution1.frequencySort(input);
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.frequencySort(input));
+        assertEquals(expected, solution2.frequencySort(input));
     }
 }
