# 1525. Number of Good Ways to Split a String

T: O(n)

S: O(n)

```java
class Solution {
    public int numSplits(String s) {
        int n = s.length();
        int[] count = new int[26];
        int[] left = new int[n];
        int[] right = new int[n];
        
        int types = 0;
        for (int i = 0; i < n; i++) {
            count[s.charAt(i) - 'a']++;
            if (count[s.charAt(i) - 'a'] == 1) {
                types++;
            }
            left[i] = types;
        }
        
        count = new int[26];
        types = 0;
        for (int i = n-1; i >= 0; i--) {
            count[s.charAt(i) - 'a']++;
            if (count[s.charAt(i) - 'a'] == 1) {
                types++;
            }
            right[i] = types;
        }
        int res = 0;
        for (int i = 0; i < n-1; i++) {
            if (left[i] == right[i+1]) {
                res++;
            }
        }
        return res;
    }
}

/*
navie: O(n^L)
s = p + q

the number of distinct letters in p and q are the same.
    
ways of split to two string = s.len - 1
    
navie check two substring has (distinct letters), [substring], [substring]
    1 <= s.length <= 10^5



O(n) solution: 3 pass

                   i
|------left--------|---------right-----|

1.
pass from left first:
get kind of char in left[i]
use char[] to record when char[x] == 1, types++

2.
pass from right:
same 

3.
final 
loop i = 0 to < n-1 (at last, there is one char need to compare, so it's < n-1)
   if (left[i] == right[i+1])                 
        ways++
*/
```

#### another explain

```
/*
sleft + sright = s) and the number of distinct letters in sleft and sright is the same.

in this two part number of distinct letters is the same

hashMap freq and separate by i

for (int i = 0 ~n)

0                   n-1
|---------i----------|

0~i, i~n-1, every i, cal the left part distinct number, cal the right part
then compare, T: O(n^2)

for (int i = 0 ~n)
   for (int j = 0~i)
   
   for (int j = i~n-1)


there is a trick when hashmap value from 0 to 1, distinct count++

only lowercase English letters.

2. T: O(n), S: O(n)
use 3 pass to handle

record distinct number in
from left : cal left[i] first
from right :cal right[i]

compare if (left[i] == right[i+1]) {
    count++;
}

*/
```

```
/*
the number of distinct letters in sleft and sright is the same.

"aacaba"

naive: 
list each combination, calulate the two part's distinct number

"aacaba" = len = 6
1 5
2 4
3 3
4 2
5 1 => n times, and calulate distinct n times  
for (i = 0 ~)
  cal len n



better: T: O(n)
record each index's distinct number 
from left
from right

      left[i] = right[i+1] => count++
      
      there are 2 ans
 [aac, aba] 
 [aaca, ba]
      o o
" a a c a b a"
  1 1 2 2 3 3
  3 3 3 2 2 1
  
  ans = 1
    o. 
  a b c d
  1 2 3 4
  4 3 2 1
  
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/string/1525.-number-of-good-ways-to-split-a-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.