ধরুন আমাদের n অক্ষর সহ একটি স্ট্রিং S আছে। S-এ শুধুমাত্র ছোট হাতের অক্ষর রয়েছে। আমাদের অবশ্যই 0 থেকে n পরিসরে একটি সংখ্যা k নির্বাচন করতে হবে, তারপর S থেকে k অক্ষর নির্বাচন করতে হবে এবং সেগুলিকে যেকোনো ক্রমে পারমিউট করতে হবে। এই প্রক্রিয়ায়, অবশিষ্ট অক্ষর অপরিবর্তিত থাকবে। আমরা ঠিক একবার এই পুরো অপারেশন সঞ্চালন. আমাদের k এর মান খুঁজে বের করতে হবে, যার জন্য S বর্ণানুক্রমিক ক্রমে সাজানো হয়।
সুতরাং, যদি ইনপুটটি S ="acdb" এর মত হয়, তাহলে আউটপুট হবে 3, কারণ 'a' সঠিক স্থানে রয়েছে এবং অবশিষ্ট অক্ষরগুলিকে পুনর্বিন্যাস করতে হবে৷
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
n := size of S d := S sort the array d j := 0 for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is not equal to d[i], then: (increase j by 1) return jরিটার্ন করুন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int solve(string S) {
int n = S.size();
string d = S;
sort(d.begin(), d.end());
int j = 0;
for (int i = 0; i < n; i++) {
if (S[i] != d[i])
j++;
}
return j;
}
int main() {
string S = "acdb";
cout << solve(S) << endl;
} ইনপুট
"acdb"
আউটপুট
3
