Skip to main content

5458. 字符串的好分割数目 [medium]

5458. 字符串的好分割数目 [medium]​

https://leetcode-cn.com/contest/biweekly-contest-31/problems/number-of-good-ways-to-split-a-string/

给你一个字符串 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

First Try​

2020-07-25

在0042题接雨水中做过类似的，一波做完左边和右边所有的边界统计，然后判断相等的坐标就行。

注意点是注意切割点是否包含当前idx，比如这里面切割点属于左边，不属于右边，因此lset.add(s[i]); left[i] = len(lset), 但是右边需要用right[j - 1] = len(rset)而不是right[j] = len(rset)

class Solution:
    def numSplits(self, s: str) -> int:
        
        left = [""] * len(s)
        right = [""] * len(s)
        lset = set()
        rset = set()
        # 切割点包含左边界，不包含右边界
        for i in range(len(s) - 1):  # 最后还要留下一个元素
            j = len(s) - 1 - i
            lset.add(s[i])
            left[i] = len(lset)
            rset.add(s[j])
            right[j - 1] = len(rset)  # 考虑不包含右边界，因此需要j - 1
        rv = 0 
        for i in range(len(s) - 1):
            if left[i] == right[i]:
                rv += 1
        return rv