Split a String in Balanced Strings

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #string, #greedy

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’

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// https://code.dennyzhang.com/split-a-string-in-balanced-strings // Basic Ideas: greedy // L -1, R +1 // When it hits 0, we increase the counter // Complexity: Time O(n), Space O(1) func balancedStringSplit(s string) int { res := 0 sum := 0 for _, ch := range s { if ch == 'R' { sum++ } else { sum-- } if sum == 0 { res++ } } return res }