Last Updated: 9 Apr, 2021
Split A String In Balanced Strings
Easy
Asked in companies
You are given a string ‘S’ consisting of an equal number of ‘L’ and ‘R’ characters only. A balanced string is a string that has an equal number of ‘L’ and ‘R’ characters. You are supposed to split the given string into balanced strings. Find the maximum amount of split balanced strings possible.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains the string ‘S’ denoting the given string.
Output Format :
For each test case, print an integer denoting the maximum amount of split balanced strings possible.
Print the output of each test case in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= |S| <= 10000
Where S[i] is either ‘L’ or ‘R’ and '|S|' is the length of the given string.
Time limit: 1 sec
Approaches
The basic idea of this approach is to iterate through the string while maintaining a variable “balance” which is initially equal to 0. Whenever we encounter ‘L we will increment the “balance” variable and similarly, whenever we encounter ‘R’ we will decrement it.
Now, let’s see an example where input string S = “LRRLRL”. Start iterating the string using a variable ‘j’.
- j = 0, since S[0] == ‘L’, increment the “balance” variable. Now, “balance” is 1.
- j = 1, since S[1] == ‘R’, decrement the “balance” variable. Now, “balance” is 0. Here we can observe that we got a balanced substring [0: 1] i.e. starting from 0th index and ending at 1th index.
- j = 2, since S[2] == ‘R’, decrement the “balance” variable. Now, ‘balance” is -1.
- j = 3, since S[3] == ‘L’, increment the “balance” variable. Now, “balance” is 0. Again we can get a balanced substring[2: 3].
- j = 4, since S[4] == ‘R’, decrement the “balance” variable. Now, “balance” is -1.
- j = 5, since S[5] == ‘L’, increment the “balance” variable. Now, “balance” is 0. Again, we can get a balanced substring[4: 5].
We observe from the above explanation that the number of times the “balance” variable becomes 0 is the maximum amount of split balanced strings possible.
The steps are as follows:
- Initialize “balance” to 0 to store the balance of the string, also initialize a variable “ans” to 0 to store the number of split balanced strings.
- Iterate from i = 0 to |S|
- If the S[i] is equal to ‘L’ increment “balance” by 1, otherwise decrement “balance” by 1.
- If the balance is equal to 0 increment “ans” by 1.
- Return “ans”.