मान लीजिए हमारे पास लोअरकेस अक्षरों की एक स्ट्रिंग S दी गई है। हम इस स्ट्रिंग को यथासंभव अधिक से अधिक भागों में विभाजित करेंगे ताकि प्रत्येक अक्षर अधिकतम एक भाग में दिखाई दे, अंत में इन भागों के आकार को दर्शाने वाले पूर्णांकों की सूची लौटाएंगे। इसलिए यदि स्ट्रिंग "ababcbacadefegdehijhklij" जैसी है, तो आउटपुट [9,7,8] होगा, क्योंकि विभाजन "ababcbaca", "defegde", "hijhklij" हैं। तो यह एक विभाजन है ताकि प्रत्येक अक्षर अधिकतम एक भाग में हो। "ababcbacadefegde", "hijhklij" जैसा विभाजन सही नहीं है, क्योंकि यह S को कम भागों में विभाजित करता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- cnt नामक एक मैप परिभाषित करें
- i को 0 से s तक की रेंज में, cnt[s[i]] := i
- j := 0, start := 0 और i := 0 और n := s का आकार
- ans नामक एक सरणी परिभाषित करें
- जब तक i < n
- j := j और cnt[s[i]] का अधिकतम
- यदि i = j, तो i - start + 1 को ans में सम्मिलित करें और start := i + 1
- i को 1 से बढ़ाएं
- ans लौटाएं
उदाहरण (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]
