Рубрики
Без рубрики

Алгоритмы решения проблемы: сбалансированные струны

Решение алгоритмов Проблемы с TK. Теги с алгоритмами, Python, Computerscience, интервью.

Этот пост является частью Алгоритмы проблемы решения ряд.

Описание проблемы

Это Разделить строку в сбалансированных струнах проблема. Описание выглядит так:

Сбалансированные струны – это те, у которых есть равное количество персонажей «L» и «R».

Учитывая сбалансированную строку S Разделить его в максимальное количество сбалансированных струн.

Верните максимальное количество разделенных сбалансированных строк.

Примеры

Input: s = "RLRRLLRLRL"
Output: 4

Input: s = "RLLLLRRRLR"
Output: 3

Input: s = "LLLLRRRR"
Output: 1

Input: s = "RLRRRLLRLL"
Output: 2

Решение

Идея здесь состоит в том, чтобы повторять строку и подсчитать каждый символ. Как мы хотим узнать максимальное количество сбалансированных строк в данной строке, нам просто нужно сравнить Л с и R S как можно скорее. Таким образом, когда они равны, это означает, что это сбалансированная строка, поэтому мы можем суммировать в максимальной переменной и снова сбросить количество.

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

Ресурсы

Оригинал: “https://dev.to/teekay/algorithms-problem-solving-balanced-strings-1c7f”