সোর্স স্ট্রিং থেকে টার্গেট স্ট্রিং গঠনের ন্যূনতম সাবসিকোয়েন্স সংখ্যা (C++)

এই সমস্যায় দুটি স্ট্রিং source এবং target দেওয়া আছে। source-র সাবসিকোয়েন্সগুলো কনক্যাট করে target বানাতে হবে। ন্যূনতম কতটি সাবসিকোয়েন্স লাগবে তা বের করতে হবে। অসম্ভব হলে -১ ফেরত দিন।

উদাহরণ

ইনপুট: source = "abc", target = "abcbc"

আউটপুট: 2

ব্যাখ্যা: "abc" + "bc" = "abcbc" (২টি সাবসিকোয়েন্স)।

অ্যালগরিদম (গিডি + বাইনারি সার্চ)

প্রথমে চেক করুন target-র সব ক্যারেক্টার source-এ আছে কিনা।
source-এ প্রতিটি ক্যারেক্টারের ইনডেক্সগুলো একটি ভেক্টরে স্টোর করুন (সর্টেড থাকে)।
target ট্রাভার্স করুন। প্রতিটি ক্যারেক্টারের জন্য বাইনারি সার্চ (upper_bound) দিয়ে করেন্ট পজিশনের পরে আর্গুмент খুঁজুন। না পেলে নতুন সাবসিকোয়েন্স শুরু করুন।

C++ প্রোগ্রাম

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

class Solution {
    bool possible(string s, string t) {
        map<char, int> m;
        for (char c : s) m[c] = 1;
        for (char c : t) if (!m[c]) return false;
        return true;
    }

public:
    int shortestWay(string s, string t) {
        if (!possible(s, t)) return -1;

        map<char, vector<int>> pos;
        for (int i = 0; i < s.size(); i++)
            pos[s[i]].push_back(i);

        int pre = -1, ans = 1;
        for (char c : t) {
            auto& v = pos[c];
            auto it = upper_bound(v.begin(), v.end(), pre);
            if (it == v.end()) {
                ans++;
                pre = v[0];
            } else {
                pre = *it;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.shortestWay("abc", "abcbc");
    return 0;
}