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'
Solution: Greedy
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: int balancedStringSplit(string s) { int b = 0; int ans = 0; for (char c : s) { b += c == 'L' ? 1 : -1; if (b == 0) ++ans; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment