এই সমস্যায় একটি স্ট্রিং দেওয়া থাকলে, সেটিকে যতটা সম্ভব বেশি পার্টিশনে ভাগ করতে হবে যাতে প্রতিটি লেটার শুধু একটি পার্টিশনে থাকে। প্রতিটি পার্টিশনের সাইজ বের করে একটি লিস্ট রিটার্ন করতে হবে।
উদাহরণস্বরূপ, স্ট্রিং "ababcbacadefegdehijhklij" এর আউটপুট হবে [9, 7, 8], কারণ পার্টিশনগুলো হবে "ababcbaca", "defegde", "hijhklij"।
সমাধানের পদ্ধতি
- একটি ম্যাপ
cntতৈরি করুন যাতে প্রতিটি ক্যারেক্টারের লাস্ট অকারেন্স (last occurrence) স্টোর করা যায়। - স্ট্রিং ট্রাভার্স করুন:
j = max(j, cnt[s[i]])। - যদি
i == jহয়, তবে একটি পার্টিশন শেষ হয়েছে। সাইজi - start + 1অ্যারে যোগ করুন এবংstart = i + 1আপডেট করুন।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << (i + 1 == v.size() ? "" : ", ");
}
cout << "]" << endl;
}
class Solution {
public:
vector<int> partitionLabels(string s) {
unordered_map<char, int> cnt;
for (int i = 0; i < s.size(); i++) cnt[s[i]] = i;
int j = 0, start = 0;
vector<int> ans;
for (int i = 0; i < s.size(); i++) {
j = max(j, cnt[s[i]]);
if (i == j) {
ans.push_back(i - start + 1);
start = i + 1;
}
}
return ans;
}
};
int main() {
Solution ob;
print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
return 0;
}
ইনপুট
"ababcbacadefegdehijhklij"
আউটপুট
[9, 7, 8]
