C++-এ ন্যূনতম স্ট্রিং পরিবর্তন: ফ্রিকোয়েন্সি মিলান

একই দৈর্ঘ্যের দুটি স্ট্রিং s এবং t দেওয়া আছে। প্রথমে s-কে যেকোনো ক্রমে সাজানো যায়। তারপর s-কে t-এ রূপান্তর করার জন্য ন্যূনতম কতটুকু ক্যারেক্টার পরিবর্তন দরকার তা বের করতে হবে।

উদাহরণ

s = "eccynue", t = "science"

s-কে "yccence" হিসেবে সাজিয়ে, 'y'-কে 's'-তে এবং দ্বিতীয় 'c'-কে 'i'-তে পরিবর্তন করলে "science" পাওয়া যায়। মোট 2টি পরিবর্তন।

সমাধানের পদ্ধতি

1. দুইটি ফ্রিকোয়েন্সি অ্যারে cnt1 (s-এর জন্য) এবং cnt2 (t-এর জন্য) তৈরি করুন।
2. প্রতিটি অক্ষর (a-z) এর জন্য, max(cnt1[i] - cnt2[i], 0) যোগ করুন।
3. মোট যোগফলই উত্তর।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(string s, string t) {
        int ret = 0;
        vector<int> cnt1(26), cnt2(26);
        for (char c : s) cnt1[c - 'a']++;
        for (char c : t) cnt2[c - 'a']++;
        for (int i = 0; i < 26; i++)
            ret += max(cnt1[i] - cnt2[i], 0);
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.solve("eccynue", "science");
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: "eccynue", "science"

আউটপুট: 2

লজিক ব্যাখ্যা

যেহেতু s-কে যেকোনো ক্রমে সাজানো যায়, আমরা শুধু অক্ষরের সংখ্যা মিলিয়ে নিতে পারি। cnt1[i] > cnt2[i] হলে সেই অতিরিক্ত অক্ষরগুলোকে পরিবর্তন করতে হবে।