ধরুন সমান সাইজের দুটি স্ট্রিং s এবং t আছে। এক স্টেপে t-এর যেকোনো ক্যারেক্টার বেছে নিয়ে অন্য ক্যারেক্টার দিয়ে রিপ্লেস করা যায়। t কে s-এর এনাগ্রাম বানাতে ন্যূনতম কত স্টেপ লাগবে তা বের করতে হবে। নোট: একটি স্ট্রিং-এর এনাগ্রাম হলো সেই স্ট্রিং-এর ক্যারেক্টারগুলোเดียর ভিন্ন অর্ডারে গঠিত স্ট্রিং।
ইনপুট - “yxy” এবং “xyx” হলে আউটপুট ১, কারণ শুধু এক ক্যারেক্টার রিপ্লেস করলেই হবে।
সমাধানের ধাপগুলো:
n := s-এ ক্যারেক্টার সংখ্যা
একটি map m তৈরি করুন s-এ উপস্থিত প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি দিয়ে ফিল করুন, আরেকটি map m2 t-এ উপস্থিত ক্যারেক্টার ফ্রিকোয়েন্সি দিয়ে
ret := n
m-এ প্রতিটি কি-ভ্যালু পেয়ার it-এর জন্য
x := min(it-এর ভ্যালু, m2[it-এর কি])
ret ১ কমান
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
