संतुलित स्ट्रिंग्स Leetcode समाधान में एक स्ट्रिंग विभाजित करें


कठिनाई स्तर आसान
में अक्सर पूछा ब्लूमबर्ग वॉलमार्ट लैब्स
लालची तार

समस्या का विवरण

इस समस्या में, हमें एक दिया जाता है स्ट्रिंग केवल 'R' और 'L' वाले वर्ण। हम एक स्ट्रिंग को संतुलित कहते हैं यदि इसमें 'R' और 'L' की समान संख्या है। हम दिए गए स्ट्रिंग को असमान सब्सट्रिंग्स में विभाजित कर सकते हैं। लक्ष्य संतुलित विभाजन स्ट्रिंग्स की अधिकतम संभव संख्या का पता लगाना है।

नोट:

  • दी गई स्ट्रिंग संतुलित है।
  • स्ट्रिंग की लंबाई सीमा में है: [१, १०००]
  • केवल 'एल' और 'आर' इनपुट में मौजूद हैं

उदाहरण

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

स्पष्टीकरण:

संतुलित स्ट्रिंग्स Leetcode समाधान में एक स्ट्रिंग विभाजित करें

 

दृष्टिकोण (लालची)

इसलिए, हमारे पास कम से कम 1 संभावित संतुलित विभाजन होगा। अब, हमें विभाजन की अधिकतम संख्या प्राप्त करने के लिए विभाजन की इस संख्या को अधिकतम करने की आवश्यकता है। सहज रूप से, हम इसे हल कर सकते हैं लालच से। हम स्ट्रिंग को आगे बढ़ाएंगे, और हर उस बिंदु पर जहां हमें 'एल' और 'आर' की समान संख्या मिली है, हम संभावित वर्गों की संख्या में वृद्धि करेंगे। इस तरह, हम एक संतुलित विभाजन स्ट्रिंग के लिए हर समाधान पर विचार करेंगे।

संतुलित स्ट्रिंग्स 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;
}

जावा प्रोग्राम

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 सॉल्यूशन में स्प्लिट ए स्ट्रींग की जटिलता का विश्लेषण

समय जटिलता

ओ (एन), एन = तार की लंबाई। समय जटिलता रैखिक है क्योंकि हम एक बार पूरे स्ट्रिंग को पीछे छोड़ते हैं।

अंतरिक्ष जटिलता 

ओ (1), क्योंकि हम केवल निरंतर मेमोरी स्पेस का उपयोग करते हैं।