C++ . में विभाजन लेबल

मान लीजिए कि हमारे पास एक स्ट्रिंग है जिसमें लोअरकेस अक्षरों का S दिया गया है। हम इस स्ट्रिंग को अधिक से अधिक भागों में विभाजित करेंगे ताकि प्रत्येक अक्षर अधिक से अधिक एक भाग में दिखाई दे, अंत में इन भागों के आकार का प्रतिनिधित्व करने वाले पूर्णांकों की एक सूची लौटाएं। इसलिए यदि स्ट्रिंग "ababcbacadefegdehijhklij" की तरह है, तो आउटपुट [9,7,8] है, क्योंकि विभाजन "ababcbaca", "defegde", "hijhklij" हैं। तो यह एक विभाजन है ताकि प्रत्येक अक्षर अधिक से अधिक एक भाग में हो। "ababcbacadefegde", "hijhklij" जैसा विभाजन सही नहीं है, क्योंकि यह S को कम भागों में विभाजित करता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सीएनटी नामक एक मानचित्र परिभाषित करें
• मैं के लिए 0 से s की सीमा में, cnt[s[i]] :=i
• j :=0, start :=0 and i :=0 and n :=size of s
• एक सरणी उत्तर परिभाषित करें
• जबकि मैं
• j :=अधिकतम j और cnt[s[i]]
• अगर i =j, तो i - start + 1 को ans में डालें और start :=i + 1
• मैं 1 से बढ़ाएँ

उदाहरण(C++)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> partitionLabels(string s) {
      map <char, int> cnt;
      for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
      int j = 0, start = 0;
      int i = 0;
      int n = s.size();
      vector <int> ans;
      while(i < n){
         j = max(j, cnt[s[i]]);
         if( i == j){
            ans.push_back(i-start+ 1);
            start = i + 1;
         }
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
}

इनपुट

"ababcbacadefegdehijhklij"

आउटपुट

[9,7,8]