DEV Community

loading...
Cover image for Algorithms Problem Solving: Balanced Strings

Algorithms Problem Solving: Balanced Strings

TK
Sharing knowledge https://leandrotk.github.io
Originally published at leandrotk.github.io ・2 min read

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 an 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 split balanced strings.

Examples

Input: s = "RLRRLLRLRL"
Output: 4

Input: s = "RLLLLRRRLR"
Output: 3

Input: s = "LLLLRRRR"
Output: 1

Input: s = "RLRRRLLRLL"
Output: 2
Enter fullscreen mode Exit fullscreen mode

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 Ls and Rs 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
Enter fullscreen mode Exit fullscreen mode

Resources

Discussion (0)