Leecode records the number of good segmentation of 1525 strings

topic

Give you a string s , A partition is called 「 Good segmentation 」 When it satisfies ： take s Divided into 2 A string p and q , They connect together to be equal to s And p and q The number of different characters in is the same .

Please return s The number of good divisions .

Example 1：

Input ：s = “aacaba”
Output ：2
explain ： All in all 5 Sort of split string “aacaba” Methods , among 2 The kind is good segmentation .
(“a”, “acaba”) The left string and the right string contain 1 And 3 Different characters .
(“aa”, “caba”) The left string and the right string contain 1 And 3 Different characters .
(“aac”, “aba”) The left string and the right string contain 2 And 2 Different characters . It's a good segmentation .
(“aaca”, “ba”) The left string and the right string contain 2 And 2 Different characters . It's a good segmentation .
(“aacab”, “a”) The left string and the right string contain 3 And 1 Different characters .
Example 2：

Input ：s = “abcd”
Output ：1
explain ： Good segmentation is to divide the string into (“ab”, “cd”) .
Example 3：

Input ：s = “aaaaa”
Output ：4
explain ： All segmentation is good segmentation .
Example 4：

Input ：s = “acbadbaada”
Output ：2

Tips ：

s Only lowercase letters .
1 <= s.length <= 10^5

answer

class Solution {
    
    public int numSplits(String s) {
    
        int n = s.length();
        int[] left = new int[n + 2];
        int[] right = new int[n + 2];
        boolean[] recLeft = new boolean[26];
        boolean[] recRight = new boolean[26];
        for (int i = 1; i <= n; i++) {
    
            int c = s.charAt(i - 1) - 'a';
            if (recLeft[c]) {
    
                left[i] = left[i - 1];
            } else {
    
                recLeft[c] = true;;
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n; i > 0; i--) {
    
            int c = s.charAt(i - 1) - 'a';
            if (recRight[c]) {
    
                right[i] = right[i + 1];
            } else {
    
                recRight[c] = true;
                right[i] = right[i + 1] + 1;
            }
        }
        int ret = 0;
        for (int i = 1; i < n; i++) {
    
            if (left[i] == right[i + 1]) {
    
                ret++;
            }
        }
        return ret;
    }
}