1525. Number of Good Ways to Split a String

T: O(n)

S: O(n)

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
  
*/