Разделение строки на сбалансированные строки Решение Leetcode


Сложный уровень Легко
Часто спрашивают в Bloomberg Walmart Labs
Жадный строка

Постановка задачи

В этой задаче нам дается строка символов, содержащих только «R» и «L». Мы называем струну сбалансированной, если в ней одинаковое количество букв R и L. Мы можем разбить данную строку на непересекающиеся подстроки. Цель состоит в том, чтобы найти максимально возможное количество сбалансированных разделенных струн.

Примечание:

  • Данная строка сбалансирована.
  • Длина строки находится в диапазоне: [1, 1000]
  • На входе присутствуют только 'L' и 'R'.

Пример

s = "RLRRLLRLRL"
4
s = "RLLLLRRRLR"
3

Объяснение:

Разделение строки на сбалансированные строки Решение Leetcode

 

Подход (Жадный)

Следовательно, у нас будет как минимум 1 возможный сбалансированный раскол. Теперь нам нужно максимизировать это количество разделов, чтобы получить максимальное количество разделов. Интуитивно мы можем это решить жадно. Мы будем перемещаться по строке, и в каждой точке, где мы получили равное количество L и R, мы будем увеличивать количество возможных секций. Таким образом, мы рассмотрим каждое решение для сбалансированной разделенной струны.

Реализация разделения строки на сбалансированное решение Leetcode

Программа C ++

#include <bits/stdc++.h>

using namespace std;

int balancedStringSplit(string s) {
    int balance = 0 , splits = 0;
    for(char &c : s) {
        balance += (c == 'L' ? -1 : 1);
        if(balance == 0)
            splits++;
    }
    return splits;
}

int main() {
    string s = "RLRRLLRLRL";
    cout << balancedStringSplit(s) << endl;
    return 0;
}

Программа Java

import java.util.*;
import java.io.*;

class balanced_splits {
    public static int balancedStringSplit(String s) {
        int balance = 0 , splits = 0;
        for(int i = 0 ; i < s.length() ; i++) {
            char c = s.charAt(i);
            balance += (c == 'L' ? -1 : 1);
            if(balance == 0)
                splits++;
        }
        return splits;
    }

    public static void main(String args[]) {
        String s = "RLRRLLRLRL";
        System.out.println(balancedStringSplit(s));
    }
}
4

Анализ сложности разбиения строки на сбалансированное решение Leetcode

Сложность времени

О (N), N = длина строки. Временная сложность линейна, потому что мы обходим всю строку один раз.

Космическая сложность 

O (1), поскольку мы используем только постоянную память.