(String categories, int k)
| 28 | // Approach 2 |
| 29 | |
| 30 | private static int findNumWaysToSplit(String categories, int k) { |
| 31 | Map<Character, Integer> charToFreq = new HashMap<>(); { |
| 32 | for (char c : categories.toCharArray()) { |
| 33 | charToFreq.put(c, charToFreq.getOrDefault(c, 0) + 1); |
| 34 | } |
| 35 | int n = categories.length(); |
| 36 | Map<Character, Integer> prefixMapItems = new HashMap<>(); |
| 37 | int numWaysToSplit = 0; |
| 38 | int numSharedChar = 0; |
| 39 | for (int i = 0; i < n; i++) { |
| 40 | char currChar = categories.charAt(i); |
| 41 | int freqLeftSide = prefixMapItems.getOrDefault(currChar, 0) + 1; |
| 42 | int freqRightSide = charToFreq.get(currChar) - freqLeftSide; |
| 43 | if (freqLeftSide != 0 && freqRightSide != 0 && !prefixMapItems.containsKey(currChar)) { |
| 44 | numSharedChar += 1; |
| 45 | } else if (freqRightSide == 0) { |
| 46 | numSharedChar -= 1; |
| 47 | } |
| 48 | if (numSharedChar > k) numWaysToSplit++; |
| 49 | prefixMapItems.put(currChar, prefixMapItems.getOrDefault(currChar, 0) + 1); |
| 50 | } |
| 51 | return numWaysToSplit; |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | |
| 56 | /* |
nothing calls this directly
no outgoing calls
no test coverage detected