原文链接: https://leetcode-cn.com/problems/number-of-good-ways-to-split-a-string

英文原文

You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are 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").

Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.

Example 4:

Input: s = "acbadbaada"
Output: 2

 

Constraints:

• s contains only lowercase English letters.
• 1 <= s.length <= 10^5

中文题目

给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 s 中好分割的数目。

 

示例 1：

输入：s = "aacaba"
输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。

示例 2：

输入：s = "abcd"
输出：1
解释：好分割为将字符串分割成 ("ab", "cd") 。

示例 3：

输入：s = "aaaaa"
输出：4
解释：所有分割都是好分割。

示例 4：

输入：s = "acbadbaada"
输出：2

 

提示：

• s 只包含小写英文字母。
• 1 <= s.length <= 10^5

通过代码

高赞题解

有哪里不明白的可以提出来，我重新说明修改

方法一、暴力解法

实现思路

本题是将字符串划分为左子字符串和右子字符串，并且两串特有的字符个数相同
我们可以直接暴力解法，直接将字符串分割为左右两部分，然后分别统计左右两部分的字符出现情况
然后判断两边特有的字符出现的个数，如果相同，那么好分割数目 + 1

实现代码模型

int len = s.length();
//这里 i = 1 是因为左半部分最少一个字符，结束条件 i < len - 1 是因为右半部分最少一个字符
for(int i = 1; i < len - 1; i++){
    //获取左边的字符情况
    //获取右边的字符情况
    //比较不同的字符情况
}

数据量 1e5，O(n^2) 就是 1e10，暴力肯定超时

方法二、滑动窗口

实现思路

方法一 的暴力解法是每次都 显式地 将字符串分割为左右，即每次都去重新遍历左右子串来获取字符情况
这样时间复杂度是 O(n^2)
但是实际上每次移动的话只是一个字符，相当于左半部分滑窗增大，右半部分滑窗减小
那么我们就可以先统计整个字符串的字符出现情况，先将整个字符串作为右半部分，然后逐一缩减，左半部分逐渐增大
使用两个数组 leftCount 和 rightCount 记录左右两部分的各个字符出现次数
使用两个变量 leftVaild 和 rightVaild 记录左右两部分不同字符的出现次数

比如左半部分字符串为 “aabac”，右半部分字符串为 “acdd”
那么 leftValid = 3，因为有 a b c 三种不同的字符
那么 rightValid = 3，因为有 a c d 三种不同的字符

我们不记录左右两边特有字符，而是记录左右两边的特有和共有字符的原因，如下

我们只需要统计左右两边不同字符的个数即可，如果相同，那么就是好字符串，无需知道是什么字符相同，什么字符不同
比如 aacaba，分割为 “aac” 和 “aba”，左边不同字符个数为 2， 右边不同字符个数为 2
即使两边都存在一个相同的字符 a,那么减去相同的字符 a 后，左边特有字符个数为 1，右边特有字符为 1，那么剩下的仍然是不同的字符个数

实现代码

class Solution {
    public int numSplits(String s) {
      
        int size = 26;
        int[] leftCount = new int[size];
        int[] rightCount = new int[size];
        int leftVaild = 0;
        int rightVaild = 0;
        //先将整个字符串作为右半部分滑窗的内容
        for(char ch : s.toCharArray()){
            int num = ch - 'a';
            if(rightCount[num] == 0){
                rightVaild++;
            }
            rightCount[num]++;
        }

        int c = 0;
        //慢慢调整左半部分滑窗，从左往右遍历，增大左半部分，缩减右半部分，进行滑窗
        for(char ch : s.toCharArray()){
            int num = ch - 'a';
            //左边没有出现过这种字符，那么左边字符 +1
            if(leftCount[num] == 0){
                leftVaild++;
            }
            //右边这是最后一次出现该字符，那么滑窗后右边字符 -1，即这种字符不会再出现在右边了
            if(rightCount[num] == 1){
                rightVaild--;
            }
            leftCount[num]++;
            rightCount[num]--;
            if(leftVaild == rightVaild){
                c++;
            }
        }
        return c;
    }
}

统计信息

通过次数	提交次数	AC比率
5668	8607	65.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言