Split A String In Balanced Strings

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
BarclaysVisa

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
LRRLRL
RRLL

Sample Output 1 :

3
1

Explanation Of Sample Output 1 :

For the first test case, the given string can be split into “LR”, “RL” and “RL”, where each substring has an equal number of ‘L’ and ‘R’. 

For the second test case, the given string can be split into “RRLL”.

Sample Input 2 :

2
LLRR
RL

Sample Output 2 :

0
1

Explanation Of Sample Output 2 :

For the first test case, the given string can be split into “LLRR”.

For the second test case, the given string can be split into “RL”.
Hint

Can you think of iterating through the string while maintaining a balance variable?

Approaches (1)
Naive approach.

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’.

  1. j = 0, since S[0] == ‘L’, increment the “balance” variable. Now, “balance” is 1.
  2. 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.
  3. j = 2, since S[2] == ‘R’, decrement the “balance” variable. Now, ‘balance” is -1.
  4. j = 3, since S[3] == ‘L’, increment the “balance” variable. Now, “balance” is 0. Again we can get a balanced substring[2: 3].
  5. j = 4, since S[4] == ‘R’, decrement the “balance” variable. Now, “balance” is -1.
  6. 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:

  1. 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.
  2. 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.
  3. Return “ans”.
Time Complexity

O(N), Where N is the length of the input string.

 

Since we are traversing through the string only once, so the overall time complexity will be O(N).

Space Complexity

O(1)

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
Split A String In Balanced Strings
Full screen
Console