দুটি স্ট্রিং a, b থেকে মার্জ স্ট্রিং বানাতে হবে যেন লেক্সিকোগ্রাফিক্যালি সবচো বড় হয়। প্রতিটি ধাপে a এবং b-এর প্রথম চেরেক্টার তুলনা করে বড়টা নিতে হবে।
অ্যালগরিদম (রিকার্সিভ)
- যদি a ≤ b হয়, তবে b[0] + merge(a, b.substr(1))
- অন্যথায় a[0] + merge(a.substr(1), b)
- বেস কেস: যেকোনো একটি খালি হলে বাকিটা যুক্ত করুন।
উদাহরণ
a="bacaa", b="abcaa" → আউটপুট: "bacabcaaaa"
ব্যাখ্যা: 'b' > 'a', তাই 'b' নেয়া হয়। তারপর 'a' vs 'a' → সমান, b[0]='b' > a[1]='a'... এইভাবে লেক্সিকোগ্রাফিক্যালি বড় স্ট্রিং বানায়।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
string largestMerge(string a, string b) {
if (a.empty() || b.empty()) return a + b;
if (a <= b) return b[0] + largestMerge(a, b.substr(1));
else return a[0] + largestMerge(a.substr(1), b);
}
int main() {
string a = "bacaa", b = "abcaa";
cout << largestMerge(a, b) << endl;
return 0;
}
আউটপুট
bacabcaaaa
