# Number of Good Ways to Split a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-good-ways-to-split-a-string)
Canonical: https://scaleengineer.com/dsa/problems/number-of-good-ways-to-split-a-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Hash Table, String
---
## Problem
You are given a string `s`.

A split is called **good** if you can split `s` into two non-empty strings `sleft` and `sright` where their concatenation is equal to `s` (i.e., `sleft + sright = s`) and the number of distinct letters in `sleft` and `sright` is the same.

Return _the number of **good splits** you can make in `s`_.

**Example 1:**

**Input:** s = "aacaba"
**Output:** 2
**Explanation:** There are 5 ways to split `"aacaba"` and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

**Example 2:**

**Input:** s = "abcd"
**Output:** 1
**Explanation:** Split the string as follows ("ab", "cd").

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of only lowercase English letters.

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. It iterates through every possible way to split the string into two non-empty parts. For each split, it calculates the number of unique characters in the left and right substrings independently and compares them. While straightforward, this method is inefficient because it repeatedly recalculates character counts for overlapping substrings.
**Time:** O(N^2), where N is the length of the string. The outer loop runs N-1 times. Inside the loop, creating substrings and iterating over them to count distinct characters takes O(N) time. Thus, the total time complexity is (N-1) * O(N) = O(N^2). · **Space:** O(N), where N is the length of the string. In each iteration, new substrings are created, which can take up to O(N) space. The HashSets take O(K) space where K is the alphabet size (a constant, 26), but the substring space dominates.
**Pros:** Very simple to understand and implement.; It is a direct and literal interpretation of the problem description.
**Cons:** Highly inefficient due to repeated work.; Creating substrings and populating hash sets in each iteration is computationally expensive.; This solution will likely result in a 'Time Limit Exceeded' error for inputs that are close to the constraints.
### Explanation
The algorithm considers every possible split point. A string of length `n` can be split in `n-1` ways. We can loop from `i = 1` to `n-1`, where `i` is the index where the split occurs. The left part of the string will be `s[0...i-1]` and the right part will be `s[i...n-1]`.

For each split, we perform the following steps:
1.  Extract the left substring, `s_left`.
2.  Extract the right substring, `s_right`.
3.  Create a `HashSet` for `s_left`. Iterate through its characters and add them to the set. The size of the set gives the number of distinct characters.
4.  Do the same for `s_right` with a new `HashSet`.
5.  If the sizes of the two sets are equal, we have found a 'good' split, so we increment a counter.

This process is repeated for all `n-1` possible splits.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numSplits(String s) {
        int n = s.length();
        int goodSplits = 0;

        // Iterate through all possible split points
        for (int i = 1; i < n; i++) {
            String s_left = s.substring(0, i);
            String s_right = s.substring(i);

            Set<Character> leftChars = new HashSet<>();
            for (char c : s_left.toCharArray()) {
                leftChars.add(c);
            }

            Set<Character> rightChars = new HashSet<>();
            for (char c : s_right.toCharArray()) {
                rightChars.add(c);
            }

            if (leftChars.size() == rightChars.size()) {
                goodSplits++;
            }
        }
        return goodSplits;
    }
}
```
### Algorithm
*   Initialize a counter `goodSplits` to 0.
*   Iterate through all possible split points `i` from `1` to `n-1`, where `n` is the length of the string `s`.
*   For each `i`, create the left substring `s_left = s.substring(0, i)` and the right substring `s_right = s.substring(i)`.
*   Use a `HashSet` to count the number of distinct characters in `s_left`.
*   Use another `HashSet` to count the number of distinct characters in `s_right`.
*   If the two counts are equal, increment `goodSplits`.
*   After the loop finishes, return `goodSplits`.

## Precomputation with Prefix and Suffix Arrays
To optimize the brute-force approach, we can avoid re-calculating the distinct character counts in every step. This approach uses precomputation. We make two passes over the string to build two arrays: one storing the count of distinct characters for every possible prefix, and another for every possible suffix. With these arrays, we can find the distinct counts for any left/right split in O(1) time.
**Time:** O(N), where N is the length of the string. We perform three separate passes over the string/arrays (one for prefixes, one for suffixes, one for checking splits), each taking O(N) time. The total time is O(N) + O(N) + O(N) = O(N). · **Space:** O(N), where N is the length of the string. We use two arrays, `prefixDistinct` and `suffixDistinct`, each of size N.
**Pros:** Much more efficient than brute force, with a linear time complexity.; The logic is still relatively easy to follow: precompute, then check.
**Cons:** Requires extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
### Explanation
The main inefficiency of the brute-force method is the repeated counting of distinct characters. We can eliminate this by pre-calculating these counts.

1.  **Prefix Counts:** We create an array, say `prefix_counts`, of the same length as the string `s`. `prefix_counts[i]` will store the number of unique characters in the substring `s[0...i]`. We can compute this array in a single pass from left to right, using a `HashSet` to keep track of the unique characters seen so far.

2.  **Suffix Counts:** Similarly, we create another array, `suffix_counts`. `suffix_counts[i]` will store the number of unique characters in the substring `s[i...n-1]`. This is computed in a single pass from right to left.

3.  **Counting Good Splits:** After both arrays are populated, we can find the number of good splits in a final, single pass. We iterate from `i = 0` to `n-2`. Each `i` represents a potential split point after the `i`-th character. The number of distinct characters in the left part (`s[0...i]`) is `prefix_counts[i]`, and for the right part (`s[i+1...n-1]`) it is `suffix_counts[i+1]`. If these two values are equal, we increment our `goodSplits` counter.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numSplits(String s) {
        int n = s.length();
        int[] prefixDistinct = new int[n];
        int[] suffixDistinct = new int[n];
        Set<Character> distinctChars = new HashSet<>();

        // Calculate prefix distinct counts
        for (int i = 0; i < n; i++) {
            distinctChars.add(s.charAt(i));
            prefixDistinct[i] = distinctChars.size();
        }

        // Clear set and calculate suffix distinct counts
        distinctChars.clear();
        for (int i = n - 1; i >= 0; i--) {
            distinctChars.add(s.charAt(i));
            suffixDistinct[i] = distinctChars.size();
        }

        int goodSplits = 0;
        // A split is after index i, so left is s[0...i] and right is s[i+1...n-1]
        for (int i = 0; i < n - 1; i++) {
            if (prefixDistinct[i] == suffixDistinct[i + 1]) {
                goodSplits++;
            }
        }

        return goodSplits;
    }
}
```
### Algorithm
*   Create an integer array `prefix` of size `n`.
*   Create a `HashSet` to track unique characters.
*   Iterate from left to right through `s`. For each index `i`, add `s.charAt(i)` to the set and store `set.size()` in `prefix[i]`.
*   Create an integer array `suffix` of size `n`.
*   Clear the `HashSet`.
*   Iterate from right to left through `s`. For each index `i`, add `s.charAt(i)` to the set and store `set.size()` in `suffix[i]`.
*   Initialize `goodSplits = 0`.
*   Iterate from `i = 0` to `n-2`. A split occurs after index `i`.
*   If `prefix[i]` (distinct chars in left part) equals `suffix[i+1]` (distinct chars in right part), increment `goodSplits`.
*   Return `goodSplits`.

## Optimized Single Pass with Frequency Arrays
This is the most optimal approach, achieving linear time complexity with constant extra space. Instead of precomputing and storing all prefix/suffix counts, we can iterate through the string once. We maintain the character counts for the left and right partitions and dynamically update them as we slide the split point from left to right.
**Time:** O(N), where N is the length of the string. We have an initial pass to populate the right frequency map (O(N)) and then a single main loop that iterates N-1 times (O(N)). The total time complexity is linear. · **Space:** O(1). The space required is for two frequency arrays of size 26 and a few integer variables. This is constant and does not scale with the length of the input string `s`.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1), as the space used does not depend on the input size.; Most efficient solution for the given constraints.
**Cons:** The logic is slightly more complex than the precomputation approach, as it involves managing the state of two partitions simultaneously.
### Explanation
This method improves upon the previous one by reducing the space complexity from O(N) to O(1).

1.  **Initialization:** We start by assuming the split is before the first character. This means the left part is empty, and the right part is the entire string. We use two frequency arrays of size 26 (for lowercase English letters), `leftFreq` and `rightFreq`. We first populate `rightFreq` by counting all characters in `s`. We also count the number of distinct characters in `s`, let's call this `rightDistinct`.

2.  **Single Pass Iteration:** We then iterate from left to right through the string, from index `i = 0` to `n-2`. In each step, we are essentially moving the character `s.charAt(i)` from the right partition to the left partition.
    *   Let `c = s.charAt(i)`.
    *   **Update Left Partition:** We update `leftFreq` for character `c`. If `c` is being added to the left partition for the first time (i.e., its count in `leftFreq` was 0), we increment a `leftDistinct` counter.
    *   **Update Right Partition:** We update `rightFreq` for character `c`. If the count of `c` in `rightFreq` becomes 0 after decrementing, it means this character is now completely gone from the right partition, so we decrement the `rightDistinct` counter.
    *   **Check for Good Split:** After each move, we compare `leftDistinct` and `rightDistinct`. If they are equal, it means the current split (after character `c`) is a good one, and we increment our result counter.

This way, we find all good splits in a single pass with only constant extra space for the frequency arrays.

```java
class Solution {
    public int numSplits(String s) {
        int n = s.length();
        int[] leftFreq = new int[26];
        int[] rightFreq = new int[26];
        int leftDistinct = 0;
        int rightDistinct = 0;

        // Initialize rightFreq and rightDistinct for the whole string
        for (char c : s.toCharArray()) {
            if (rightFreq[c - 'a'] == 0) {
                rightDistinct++;
            }
            rightFreq[c - 'a']++;
        }

        int goodSplits = 0;
        // Iterate through possible split points, moving one char from right to left
        for (int i = 0; i < n - 1; i++) {
            char c = s.charAt(i);

            // Update left side
            if (leftFreq[c - 'a'] == 0) {
                leftDistinct++;
            }
            leftFreq[c - 'a']++;

            // Update right side
            rightFreq[c - 'a']--;
            if (rightFreq[c - 'a'] == 0) {
                rightDistinct--;
            }

            // Check for good split
            if (leftDistinct == rightDistinct) {
                goodSplits++;
            }
        }
        return goodSplits;
    }
}
```
### Algorithm
*   Create two frequency arrays, `leftFreq` and `rightFreq`, of size 26, initialized to 0.
*   Initialize `leftDistinct = 0` and `rightDistinct = 0`.
*   First, iterate through the entire string `s` to populate `rightFreq` and calculate the initial `rightDistinct` count.
*   Initialize `goodSplits = 0`.
*   Iterate through the string from `i = 0` to `n-2` to simulate moving the split point. Let the current character be `c`.
*   For each character `c`, move it from the right partition to the left:
    *   Increment `leftFreq[c - 'a']`. If its count becomes 1, increment `leftDistinct`.
    *   Decrement `rightFreq[c - 'a']`. If its count becomes 0, decrement `rightDistinct`.
*   After updating the counts, if `leftDistinct` equals `rightDistinct`, increment `goodSplits`.
*   Return `goodSplits`.

# Solutions
### Java

```java
class Solution { public int numSplits ( String s ) { Map < Character , Integer > cnt = new HashMap <>(); for ( char c : s . toCharArray ()) { cnt . merge ( c , 1 , Integer: : sum ); } Set < Character > vis = new HashSet <>(); int ans = 0 ; for ( char c : s . toCharArray ()) { vis . add ( c ); if ( cnt . merge ( c , - 1 , Integer: : sum ) == 0 ) { cnt . remove ( c ); } if ( vis . size () == cnt . size ()) { ++ ans ; } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int numSplits(string s) {
    unordered_map<char, int> cnt;
    for (char &c : s) {
      ++cnt[c];
    }
    unordered_set<char> vis;
    int ans = 0;
    for (char &c : s) {
      vis.insert(c);
      if (--cnt[c] == 0) {
        cnt.erase(c);
      }
      ans += vis.size() == cnt.size();
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numSplits(self, s: str) -> int: cnt = Counter(s) vis = set() ans = 0 for c in s: vis . add(c) cnt[c] -= 1 if cnt[c] == 0: cnt . pop(c) ans += len(vis) == len(cnt) return ans

```