Розділіть рядок у збалансованому рішенні Leetcode Solution  


Рівень складності Легко
Часто запитують у Bloomberg Лабораторії Walmart
алгоритми кодування Жадібний інтерв'ю інтерв'юпідготовка LeetCode LeetCodeSolutions рядок

Постановка проблеми  

У цій задачі нам дано a рядок символів, що містять лише "R" і "L". Ми називаємо рядок збалансованим, якщо він має однакову кількість 'R' і 'L'. Ми можемо розділити даний рядок на непересічні підрядки. Мета - знайти максимально можливу кількість збалансованих розділених рядків.

Примітка:

  • Наведений рядок збалансований.
  • Довжина рядка лежить в межах: [1, 1000]
  • На вході присутні лише "L" і "R"

Приклад

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

Пояснення:

Розділіть рядок у збалансованому рішенні Leetcode SolutionPin

 

Підхід (Жадібний)  

Тому ми матимемо принаймні 1 можливий збалансований розкол. Тепер нам потрібно максимізувати цю кількість поділів, щоб отримати максимальну кількість розділів. Інтуїтивно ми можемо це вирішити жадібно. Ми пройдемо по рядку, і в кожній точці, де ми отримали однакову кількість 'L' і 'R', ми будемо збільшувати кількість можливих розділів. Таким чином, ми розглянемо кожне рішення для збалансованого розділеного струна.

Реалізація розділення рядка у збалансованому рішенні Leetcode Solution

Програма С ++

#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

Аналіз складності розбиття рядка у збалансованому рішенні Леткод рішення

Складність часу

O (N), N = довжина рядка. Складність у часі лінійна, оскільки ми проходимо один раз цілий рядок.

Дивись також
Перетин двох масивів II Рішення Leetcode

Складність простору 

O (1), оскільки ми використовуємо лише постійний простір пам’яті.

1