Split a String in Balanced Strings
This post is part of the Algorithms Problem Solving series.
Problem description
This is the Split a String in Balanced Strings problem. The description looks like this:
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.
Examples
Input: s = "RLRRLLRLRL"
Output: 4
Input: s = "RLLLLRRRLR"
Output: 3
Input: s = "LLLLRRRR"
Output: 1
Input: s = "RLRRRLLRLL"
Output: 2
Solution
The idea here is to iterate through the string and count each
character. As we want to know the maximum number of balanced strings
in the given string, we just need to compare the L
s and
R
s as soon as possible. That way, when they are equal, it
means that it is a balanced string, so we can sum in the max variable
and reset the count again.
def balanced_string_split(s):
els = 0
ares = 0
max = 0
for char in s:
if char == 'L':
els += 1
else:
ares += 1
if els == ares:
max += 1
els = 0
ares = 0
return max
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!