Q1221 分割平衡字符串-简单-括号匹配

1221. 分割平衡字符串

Question

在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

返回可以通过分割得到的平衡字符串的 最大数量 。

Example 1:

输入：s = "RLRRLLRLRL" 输出：4 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

Example 2:

输入：s = "RLLLLRRRLR" 输出：3 解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

提示：

• 1 <= s.length <= 1000
• s[i] = 'L' 或 'R'
• s 是一个平衡字符串
• 分割得到的每个字符串都必须是平衡字符串。

Approach 1: 前缀和

本题目的思路很简单，从以下几点分析：

• 题目只考虑分割，意味着不打乱字母顺序，分割的序列必然上大序列的子序列；
• 子序列不考虑是否要对称，因此自用考虑子序列内的字符数目相等；
• 题目限定了字符串s中只包含“L”和“R”，所以不用考虑有意外的符号出现；

代码如下，在for循环内考虑L与R个数相等时子序列个数加1：

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        res,L,R=0,0,0
        for i in range(len(s)):
            if s[i] =='L':
                L+=1
            elif s[i]=='R':
                R+=1
            if L==R and L!=0:
                res+=1
                # 如果s中不限定只包含字符LR，则需置零L和R
        return res

def main():
    s = "RLRRLLRLRL"
    solution=Solution().balancedStringSplit(s)
    print(solution)

if __name__ == "__main__":
    main()

复杂度分析

• 时间复杂度：O(n)，n是字符数量。
• 空间复杂度：O(1)，只使用了几个变量。