Minimum Substring Partition of Equal Character Frequency

• Create a DP array dp of size n + 1, where n is the length of the string s.
• dp[i] will store the minimum number of balanced partitions for the prefix s[0...i-1].
• Initialize dp[0] = 0 and dp[i] to a large value (e.g., i) for i > 0.
• Iterate i from 1 to n:
  • For each i, iterate j from 0 to i-1.
  • In the inner loop, extract the substring sub = s.substring(j, i).
  • Check if sub is a balanced string by creating a frequency map and verifying that all characters present have the same frequency.
  • If sub is balanced, it represents a valid final partition for the prefix of length i. We can then update dp[i] with the formula: dp[i] = min(dp[i], dp[j] + 1).
• After the loops complete, dp[n] will hold the minimum number of partitions for the entire string s.

We build a solution from the ground up using dynamic programming. Let dp[i] be the minimum number of partitions for the prefix s[0...i-1]. Our goal is to find dp[n]. The base case is dp[0] = 0, as an empty string requires no partitions.

To compute dp[i], we consider all possible substrings s[j...i-1] that can end at index i-1. For each j from 0 to i-1, we check if the substring s[j...i-1] is balanced. This check is done using a helper function that counts character frequencies within the substring and ensures all non-zero counts are equal.

If s[j...i-1] is indeed balanced, we have found a valid partition. The total number of partitions for s[0...i-1] would be 1 (for s[j...i-1]) plus the minimum partitions for the preceding part of the string, s[0...j-1], which is already computed and stored in dp[j]. We update dp[i] by taking the minimum over all valid j's: dp[i] = min(dp[i], dp[j] + 1).

This process is repeated for all i from 1 to n. The main drawback is that for each pair of (i, j), we create and analyze the substring from scratch, leading to a cubic time complexity.

1class Solution {2    public int minimumSubstringsInPartition(String s) {3        int n = s.length();4        int[] dp = new int[n + 1];5        for (int i = 1; i <= n; i++) {6            dp[i] = i; // Worst case: partition into i single characters7        }8        dp[0] = 0;9 10        for (int i = 1; i <= n; i++) {11            for (int j = 0; j < i; j++) {12                // Substring from index j to i-113                if (isBalanced(s, j, i)) {14                    dp[i] = Math.min(dp[i], dp[j] + 1);15                }16            }17        }18        return dp[n];19    }20 21    private boolean isBalanced(String s, int start, int end) {22        int[] counts = new int[26];23        for (int i = start; i < end; i++) {24            counts[s.charAt(i) - 'a']++;25        }26 27        int freq = -1;28        for (int count : counts) {29            if (count > 0) {30                if (freq == -1) {31                    freq = count;32                } else if (freq != count) {33                    return false;34                }35            }36        }37        return true;38    }39}

• Create a DP array dp of size n + 1 and initialize it as in the previous approach (dp[0] = 0, dp[i] = i).
• Iterate i from 1 to n to compute dp[i].
• For each i, start an inner loop with j iterating backwards from i-1 down to 0.
• Maintain a single frequency map (counts array) for the current outer loop i.
• In the inner loop (for j), you are considering substrings s[j...i-1]. As j decreases, the substring extends to the left.
• Update the counts array by incrementing the count for s.charAt(j).
• After updating, check if the counts array represents a balanced string. This check takes constant time (O(26)).
• If it is balanced, update dp[i] = min(dp[i], dp[j] + 1).
• Return dp[n] as the final result.

The core idea is to eliminate the redundant work of the O(n^3) approach. We still use a DP array dp where dp[i] is the minimum partitions for s[0...i-1].

The optimization comes from how we structure the inner loops. For each i from 1 to n, we want to find the best split point j. Instead of iterating j forward and re-evaluating the substring s[j...i-1] each time, we iterate j backwards from i-1 down to 0.

For a fixed i, we initialize a frequency map. Then, as j goes from i-1 down to 0, we are considering the substrings s[i-1...i-1], s[i-2...i-1], s[i-3...i-1], and so on. We can maintain the frequency map for this growing substring by simply adding the new character s.charAt(j) at each step. After each addition, we perform a quick O(1) check on the frequency map to see if it represents a balanced string. If it does, we apply the DP transition dp[i] = Math.min(dp[i], dp[j] + 1).

This way, the check for a balanced substring of length k is done in O(1) time instead of O(k), making the overall algorithm much faster and suitable for the given constraints.

1class Solution {2    public int minimumSubstringsInPartition(String s) {3        int n = s.length();4        int[] dp = new int[n + 1];5        6        // dp[i] stores the minimum partitions for prefix s[0...i-1]7        dp[0] = 0;8        for (int i = 1; i <= n; i++) {9            dp[i] = i; // Initialize with worst case (i partitions of length 1)10        }11 12        for (int i = 1; i <= n; i++) {13            int[] counts = new int[26];14            // Iterate backwards from i-1 to check for balanced substrings ending at i-1.15            // j is the start index of the potential last substring.16            for (int j = i - 1; j >= 0; j--) {17                // Add current character to the frequency map for substring s[j...i-1]18                counts[s.charAt(j) - 'a']++;19                20                // Check if this substring is balanced21                if (isBalanced(counts)) {22                    // If s[j...i-1] is balanced, we can make a partition.23                    // The number of partitions would be 1 (for this substring) +24                    // the minimum partitions for the prefix s[0...j-1], which is dp[j].25                    dp[i] = Math.min(dp[i], dp[j] + 1);26                }27            }28        }29        return dp[n];30    }31 32    private boolean isBalanced(int[] counts) {33        int freq = 0; // Stores the frequency of the first character group found34        for (int count : counts) {35            if (count > 0) {36                if (freq == 0) {37                    freq = count;38                } else if (freq != count) {39                    return false;40                }41            }42        }43        return true;44    }45}