1221. Split a String in Balanced Strings

LeetCode Link (opens in a new tab)

string greedy

Description

Balanced strings are those that have an equal quantity of 'L' and 'R' characters.

Given a balanced string s, split it into some number of substrings such that:

• Each substring is balanced. Return the maximum number of balanced strings you can obtain.

Example cases

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 = "RLRRRLLRLL"
• Output: 2
• Explanation: s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'. Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.

Example 3:

• Input: s = "LLLLRRRR"
• Output: 1
• Explanation: s can be split into "LLLLRRRR".

Constraints

• 2 <= s.length <= 1000
• s[i] is either 'L' or 'R'.
• s is a balanced string.

Approach

이 문제는 'L'과 'R'로 이루어진 string 's'를 모든 substrings가 balance가 되도록 쪼갰을 때, substring의 최대개수를 구하는 문제이다. 문제에서 balance는 L과 R의 개수가 동일할 때를 말한다. greedy 접근법으로 풀 수 있는데, 이미 전체 문자열이 balance라 balance인 substring을 제거했을 때 나머지 string도 balance를 유지함을 보장할 수 있다. 그래서 현재 substring이 balance면 바로 +1 해줘도 된다. 즉, 현재 L 카운트와 R 카운트가 같다면 답을 +1 하는 식으로 linear time에 해결할 수 있다.

Solution Code

var balancedStringSplit = function(s) {
    let l = 0
    let r = 0
    let ans = 0
    for (let i = 0; i < s.length; i += 1) {
        if (s[i] === 'L') {
            l += 1
        } else {
            r += 1
        }
 
        if (l === r) {
            ans += 1
            l = 0
            r = 0
        }
    }
 
    return ans
};

Complexity

• time complexity : O(n)
• space complexity : O(1)