ধরুন আমাদের দুটি সমান-আকারের স্ট্রিং s এবং t আছে। এক ধাপে আমরা t এর যেকোনো অক্ষর বেছে নিতে পারি এবং অন্য অক্ষর দিয়ে প্রতিস্থাপন করতে পারি। s-এর একটি অ্যানাগ্রাম তৈরি করতে আমাদের ন্যূনতম সংখ্যক ধাপ বের করতে হবে। দ্রষ্টব্য:একটি স্ট্রিং এর একটি অ্যানাগ্রাম হল একটি স্ট্রিং যাতে একই অক্ষর থাকে একটি ভিন্ন (বা একই) ক্রম।
সুতরাং ইনপুট যদি হয় - “yxy” এবং “xyx”, তাহলে আউটপুট হবে 1, কারণ শুধুমাত্র একটি অক্ষর প্রতিস্থাপন করতে হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=s
এ অক্ষরের আকার -
একটি মানচিত্র m তৈরি করুন এবং s-এ উপস্থিত প্রতিটি অক্ষরের ফ্রিকোয়েন্সি দিয়ে এটি পূরণ করুন, আরেকটি মানচিত্র m2 তৈরি করুন এবং t-এ উপস্থিত প্রতিটি অক্ষরের ফ্রিকোয়েন্সি দিয়ে এটি পূরণ করুন
-
ret :=n
-
প্রতিটি কী-মানের জন্য এটি m
-এ যুক্ত করুন-
x :=এর সর্বনিম্ন মান এবং m2 [এর মান]
-
1 দ্বারা ret কমান
-
-
রিটার্ন রিটার্ন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSteps(string s, string t) {
int n = s.size();
map <char, int> m1;
for(int i = 0; i < s.size(); i++){
m1[s[i]]++;
}
int ret = n;
map <char, int> m2;
for(int i = 0; i < t.size(); i++){
m2[t[i]]++;
}
map <char, int> :: iterator it = m1.begin();
while(it != m1.end()){
//cout << it->first << " " << it->second << " " << m2[it->first] << endl;
int x = min(it->second, m2[it->first]);
ret -= x;
it++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.minSteps("yxy", "xyx"));
} ইনপুট
"yxy" "xyx"
আউটপুট
1
