સંતુલિત સ્ટ્રિંગ્સ લીટકોડ સોલ્યુશનમાં એક શબ્દમાળાને વિભાજિત કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે બ્લૂમબર્ગ વોલમાર્ટ લેબ્સ
લોભી શબ્દમાળા

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને એ શબ્દમાળા અક્ષરો, જેમાં ફક્ત 'R' અને 'L' હોય છે. જો આપણે શબ્દમાળાને સંતુલિત કહીએ છીએ, જો તેમાં 'આર' અને 'એલ' ની સમાન સંખ્યા હોય. આપેલ સ્ટ્રિંગને ડિજ disઇંટ સબસ્ટ્રિંગ્સમાં વિભાજીત કરી શકીએ છીએ. લક્ષ્ય એ છે કે સંતુલિત વિભાજિત તારની મહત્તમ શક્ય સંખ્યા શોધવી.

નૉૅધ:

  • આપેલ શબ્દમાળા સંતુલિત છે.
  • શબ્દમાળાની લંબાઈ આ શ્રેણીમાં છે: [1, 1000]
  • ઇનપુટમાં ફક્ત 'એલ' અને 'આર' હાજર છે

ઉદાહરણ

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

સમજૂતી:

સંતુલિત સ્ટ્રિંગ્સ લીટકોડ સોલ્યુશનમાં એક શબ્દમાળાને વિભાજિત કરો

 

અભિગમ (લોભી)

તેથી, અમારી પાસે ઓછામાં ઓછું 1 શક્ય સંતુલિત વિભાજન હશે. હવે, પાર્ટીશનની મહત્તમ સંખ્યા મેળવવા માટે આપણે આ સંખ્યાને વધુને વધુ સ્પ્લિટ કરવાની જરૂર છે. સાહજિક રીતે, અમે તેને હલ કરી શકીએ છીએ લોભી. અમે શબ્દમાળાને વટાવીશું, અને દરેક બિંદુએ જ્યાં અમને 'L's' અને 'R' ની સમાન સંખ્યા પ્રાપ્ત થઈ છે, અમે શક્ય વિભાગોની સંખ્યામાં વધારો કરીશું. આ રીતે, અમે સંતુલિત વિભાજિત શબ્દમાળા માટેના દરેક ઉકેલો પર વિચાર કરીશું.

સંતુલિત સ્ટ્રિંગ્સ લીટકોડ સોલ્યુશનમાં સ્પ્લિટ એ સ્ટ્રિંગની અમલીકરણ

સી ++ પ્રોગ્રામ

#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;
}

જાવા પ્રોગ્રામ

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

સંતુલિત સ્ટ્રિંગ્સ લીટકોડ સોલ્યુશનમાં સ્પ્લિટ એ સ્ટ્રિંગનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), એન શબ્દમાળા લંબાઈ. સમયની જટિલતા રેખીય છે કારણ કે અમે એકવાર આખા શબ્દમાળાને વટાવીએ છીએ.

અવકાશ જટિલતા 

ઓ (1), કારણ કે આપણે ફક્ત સતત મેમરી સ્પેસનો ઉપયોગ કરીએ છીએ.