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) —

推荐阅读:
C++ Algorithms to Find Pair of Sum Given a Collection of Numbers  How to Implement strStr() function in C++?  How to Check Valid Word Abbreviation in C++?  CloudFlare Enterprise Plan Overview  Powerful Integers by Bruteforce Algorithm using C++  How to Check if Any Three Points can Make a Triangle?  How to Convert Set to Vector in C++?  Peeple App Embodies the Worst of Social Media  10 Best Writing Quotes for Bloggers  Will Dorsey be Twitter’s Next CEO? 
评论列表
添加评论