সমস্যা বিবরণ
একটি স্ট্রিং দেওয়া আছে। স্ট্রিং-এর ক্যারেক্টার রি-অ্যারেঞ্জ করতে হবে যাতে স্বর (vowel) এবং ব্যঞ্জন (consonant) ব랬 বarlos পজিশনে থাকে। যদি সম্ভব না হয় তবে "no such string" দেখাতে হবে। স্বর ও ব্যঞ্জনগুলো তাদের নিজস্ব অর্ডার রক্ষা করবে। একাধিক সমাধান হলে লেক্সিকোগ্রাফিক্যালি ছোটটি দেখাতে হবে।
উদাহরণ
Input : Tutorial Output : Tutorila Input : onse Output : nose (দুটি সম্ভাব্য আউটপুট: "nose" ও "ones", "nose" লেক্সিকোগ্রাফিক্যালি ছোট)
অ্যালগরিদম
- স্ট্রিং-এ স্বর ও ব্যঞ্জন গণনা করুন।
- যদি কাউন্টের পার্থক্য >= 2 হয়, "Not Possible" রিটার্ন করুন।
- স্বর বেশি হলে প্রথম স্বর প্রথমে দেখিয়ে বাকি স্ট্রিং-এ রিকার্সন।
- ব্যঞ্জন বেশি হলে প্রথম ব্যঞ্জন প্রথমে দেখিয়ে বাকি স্ট্রিং-এ রিকার্সন।
- দুটি কাউন্ট সমান হলে প্রথম স্বর ও ব্যঞ্জন তুলনা কর ছোটটি প্রথমে দেখান।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch1) {
return (ch1=='a' || ch1=='e' || ch1=='i' || ch1=='o' || ch1=='u');
}
string createAltStr(string str1, string str2, int start1, int l1) {
string finalStr1 = "";
for (int i=0, j=start1; j<l1; i++, j++)
finalStr1 = (finalStr1 + str1.at(i)) + str2.at(j);
return finalStr1;
}
string findAltStr(string str3) {
int nv1 = 0, nc1 = 0;
string vstr1 = "", cstr1 = "";
int l1 = str3.size();
for (int i=0; i<l1; i++) {
char ch1 = str3.at(i);
if (isVowel(ch1)) { nv1++; vstr1 += ch1; }
else { nc1++; cstr1 += ch1; }
}
if (abs(nv1-nc1) >= 2) return "no such string";
if (nv1 > nc1)
return (vstr1.at(0) + createAltStr(cstr1, vstr1, 1, nv1));
if (nc1 > nv1)
return (cstr1.at(0) + createAltStr(vstr1, cstr1, 1, nc1));
if (cstr1.at(0) < vstr1.at(0))
return createAltStr(cstr1, vstr1, 0, nv1);
return createAltStr(vstr1, cstr1, 0, nc1);
}
int main() {
string str3 = "Tutorial";
cout << findAltStr(str3);
return 0;
}
আউটপুট
Tutorila
Time Complexity: O(n)
