add 1781

fishercoder1534 · fishercoder1534 · commit eaf4941f1ede · 2021-03-06T16:12:29.000-08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1781|[Sum of Beauty of All Substrings](https://leetcode.com/problems/sum-of-beauty-of-all-substrings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1781.java) ||Medium|HashTable, String|
 |1780|[Check if Number is a Sum of Powers of Three](https://leetcode.com/problems/check-if-number-is-a-sum-of-powers-of-three/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1780.java) ||Medium|Math, Backtracking, Recursion|
 |1779|[Find Nearest Point That Has the Same X or Y Coordinate](https://leetcode.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1779.java) ||Easy|Array|
 |1774|[Closest Dessert Cost](https://leetcode.com/problems/closest-dessert-cost/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1774.java) ||Medium|Greedy|
diff --git a/src/main/java/com/fishercoder/solutions/_1781.java b/src/main/java/com/fishercoder/solutions/_1781.java
@@ -0,0 +1,42 @@
+package com.fishercoder.solutions;
+
+public class _1781 {
+    public static class Solution1 {
+        /**
+         * credit: https://leetcode.com/problems/sum-of-beauty-of-all-substrings/discuss/1096380/Java-or-T%3A-O(N2)-or-S%3A-O(1)-Get-the-beauty-of-all-substrings-and-sum-them
+         */
+        public int beautySum(String s) {
+            int sum = 0;
+            for (int i = 0; i < s.length(); i++) {
+                int[] charCount = new int[26];
+                for (int j = i; j < s.length(); j++) {
+                    charCount[s.charAt(j) - 'a']++;
+                    //get beauty of s.substring(i, j)
+                    int beauty = getMaxCount(charCount) - getMinCount(charCount);
+                    sum += beauty;
+                }
+            }
+            return sum;
+        }
+
+        private int getMinCount(int[] charCount) {
+            int min = Integer.MAX_VALUE;
+            for (int i = 0; i < 26; i++) {
+                if (charCount[i] != 0) {
+                    min = Math.min(min, charCount[i]);
+                }
+            }
+            return min;
+        }
+
+        private int getMaxCount(int[] charCount) {
+            int max = 0;
+            for (int i = 0; i < 26; i++) {
+                if (charCount[i] != 0) {
+                    max = Math.max(max, charCount[i]);
+                }
+            }
+            return max;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1781Test.java b/src/test/java/com/fishercoder/_1781Test.java
@@ -0,0 +1,22 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1781;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1781Test {
+    private static _1781.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1781.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(5, solution1.beautySum("aabcb"));
+    }
+
+}
