ধরুন আমাদের একটি স্ট্রিং আছে, আমাদের ফ্রিকোয়েন্সির উপর ভিত্তি করে অক্ষরগুলি সাজাতে হবে। তাই স্ট্রিং যদি "abbbacbcc" এর মত হয়, তাহলে আউটপুট হবে "bbbbcccaa"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- v নামে জোড়ার একটি অ্যারে তৈরি করুন, একটি মানচিত্র তৈরি করুন m
- স্ট্রিং-এর সমস্ত অক্ষরের জন্য,
- m[অক্ষর] এর মান 1 দ্বারা বৃদ্ধি করুন
- i :=মানচিত্রের প্রথম উপাদান
- যখন মানচিত্রের উপাদান আছে
- v তে (i.second, i.first) ঢোকান
- এবং পরবর্তী উপাদানের দিকে নির্দেশ করতে i বাড়ান
- ভেক্টর বাছাই করুন v
- উত্তর :=একটি খালি স্ট্রিং
- এর জন্য i :=0 থেকে v
- এর আকার
- t :=v[i] এর প্রথম উপাদান
- যদিও t 0
- নয়
- উত্তর :=উত্তর + v[i] এর দ্বিতীয় অংশ
- t 1 কমিয়ে দিন
- উত্তর ফেরত দিন
উদাহরণ
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(pair <int, char> a, pair <int, char> b){
return a.first < b.first;
}
string frequencySort(string s) {
vector < pair <int, char> > v;
map <char, int> m;
for(int i = 0; i < s.size(); i++){
m[s[i]]++;
}
map <char, int> :: iterator i = m.begin();
while(i != m.end()){
v.push_back({i->second, i->first});
i++;
}
sort(v.rbegin(), v.rend(), cmp);
string ans = "";
for(int i = 0; i < v.size(); i++){
int t = v[i].first;
while(t--)ans += v[i].second;
}
return ans;
}
};
main(){
Solution ob;
cout << ob.frequencySort("abbbacbcc");
} ইনপুট
"abbbacbcc"
আউটপুট
bbbbcccaa
