ধরুন আমাদের কাছে ছোট হাতের অক্ষরের একটি স্ট্রিং S দেওয়া আছে। আমরা এই স্ট্রিংটিকে যতটা সম্ভব অনেক অংশে ভাগ করব যাতে প্রতিটি অক্ষর সর্বাধিক একটি অংশে উপস্থিত হয়, অবশেষে এই অংশগুলির আকারের প্রতিনিধিত্বকারী পূর্ণসংখ্যাগুলির একটি তালিকা ফেরত দেয়। সুতরাং স্ট্রিং যদি "ababcbacadefegdehijhklij" এর মত হয়, আউটপুট হবে [9,7,8], কারণ পার্টিশনগুলি হল "ababcbaca", "defegde", "hijhklij"। সুতরাং এটি একটি বিভাজন যাতে প্রতিটি অক্ষর সর্বাধিক একটি অংশে ঘটে। একটি পার্টিশন যেমন "ababcbacadefegde", "hijhklij" সঠিক নয়, কারণ এটি S কে কম অংশে বিভক্ত করে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- cnt নামে একটি মানচিত্র সংজ্ঞায়িত করুন
- আমি 0 থেকে s রেঞ্জের জন্য, cnt[s[i]] :=i
- j :=0, start :=0 এবং i :=0 এবং n :=s এর আকার
- একটি অ্যারে উত্তর সংজ্ঞায়িত করুন
- যখন আমি
- j :=j এবং cnt[s[i]]
এর সর্বোচ্চ- যদি i =j, তাহলে i – start + 1 ans এ ঢুকিয়ে শুরু করুন :=i + 1
- i 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]
