题目描述
思路

leetcode - daily - 1221. 分割平衡字符串

题目描述

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

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

注意:分割得到的每个字符串都必须是平衡字符串。

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

 

示例 1:

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

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

输入:s = "LLLLRRRR"
输出:1
解释:s 只能保持原样 "LLLLRRRR".
示例 4:

输入:s = "RLRRRLLRLL"
输出:2
解释:s 可以分割为 "RL"、"RRRLLRLL" ,每个子字符串中都包含相同数量的 'L' 和 'R' 。
 

提示:

1 <= s.length <= 1000
s[i] = 'L' 或 'R'
s 是一个 平衡 字符串

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/split-a-string-in-balanced-strings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

主要思路: 贪心

阅读题意,可以得到以下信息

  1. 给定字符串 S 是一个平衡字符串, 也就是说 Count(‘L’) === Count(‘R’), 如果把 L 看作 1, R 看作-1, 那么可以认为一个平衡字符串的前缀和为 0
  2. 如果将一个平衡字符串 S 拆为 [a, b] 两个子串,如果 a 是平衡字符串,那么 b 一定是字符串。根据 1, Sum(s) === 0, Sum(a) === 0, Sum(b) = Sum(s) - Sum(a) = 0

求字符串 s 可以拆分的最多平衡字符串个数,可以通过贪心,具体算法为

  1. 遍历字符串 S,计算字符串 S 的前缀和 prefix
  2. 如果 prefix === 0, 则平衡子字符串数 count = count + 1
/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function (s) {
  let prefix = 0,
    count = 0;

  for (let char of s) {
    prefix += char === 'L' ? 1 : -1;
    count += prefix === 0;
  }

  return count;
};
  • 时间复杂度: $O(N)$, N 为 s 的长度
  • 空间复杂度: $O(1)$

feiker 少年起而行之