---
# System prepended metadata

title: 1525. Number of Good Ways to Split a String
tags: [Leetcode, Three Pass, Medium, Greedy]

---

# 1525. Number of Good Ways to Split a String
###### tags: `Leetcode` `Medium` `Greedy` `Three Pass`
Link: https://leetcode.com/problems/number-of-good-ways-to-split-a-string/description/
## 思路
```left[i]```表示```s[0:i]```有多少个unique character
```right[i]```表示```s[i+1:-1]```有多少个unique character
所以最后我们只要找到有多少个位置```left[i]==right[i]```
## Code
```java=
class Solution {
    public int numSplits(String s) {
        int n = s.length();
        int[] cnt = new int[26];
        int uni = 0;
        int[] leftUni = new int[n];
        int[] rightUni = new int[n]; 
        for(int i=0; i<n; i++){
            if(cnt[s.charAt(i)-'a']==0) uni++;
            leftUni[i] = uni;
            cnt[s.charAt(i)-'a']++;
        }
        Arrays.fill(cnt, 0);
        uni = 0;
        for(int i=n-2; i>=0; i--){
            if(cnt[s.charAt(i+1)-'a']==0) uni++;
            rightUni[i] = uni;
            cnt[s.charAt(i+1)-'a']++;
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            if(leftUni[i]==rightUni[i]) ans++;
        }
        return ans;
    }
}
```