How to Split a String in Balanced Strings?
- 时间:2020-09-18 17:26:09
- 分类:网络文摘
- 阅读:94 次
Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters. Given a balanced string s split it in the maximum amount of balanced strings. Return the maximum amount of splitted balanced strings.
Example 1:
Input: s = “RLRRLLRLRL”
Output: 4
Explanation: s can be split into “RL”, “RRLL”, “RL”, “RL”, each substring contains same number of ‘L’ and ‘R’.Example 2:
Input: s = “RLLLLRRRLR”
Output: 3
Explanation: s can be split into “RL”, “LLLRRR”, “LR”, each substring contains same number of ‘L’ and ‘R’.Example 3:
Input: s = “LLLLRRRR”
Output: 1
Explanation: s can be split into “LLLLRRRR”.Constraints:
1 <= s.length <= 1000
s[i] = ‘L’ or ‘R’Hints:
Loop from left to right maintaining a balance variable when it gets an L increase it by one otherwise decrease it by one.
Whenever the balance variable reaches zero then we increase the answer by one.
Balancing Parentheses Algorithm
This is quite similar to the Parentheses algorithms that we can use a variable to keep tracking the balance i.e. when we meet a left Parentheses, we increment the balance or decrement it otherwise. If the balance becomes zero, we increment the split count.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: int balancedStringSplit(string s) { int bal = 0, ans = 0; for (const auto &n: s) { if (n == 'L') { bal ++; } else { bal --; } if (bal == 0) { ans ++; } } return ans; } }; |
class Solution { public: int balancedStringSplit(string s) { int bal = 0, ans = 0; for (const auto &n: s) { if (n == 'L') { bal ++; } else { bal --; } if (bal == 0) { ans ++; } } return ans; } };
O(N) time where N is the size of the input string. O(1) constant space is required.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:买车的分数问题 数列求和之公式求和 数列求和之二——分组求和 数列求和之三——拆项消去求和 数列求和之四——错位相减求和 笛卡尔与直角坐标系 两道有关和尚的问题 一道关于步行与跑步的问题 少年华罗庚 15届华罗庚金杯少年数学邀请赛初赛试题及解答
- 评论列表
-
- 添加评论