सी ++ प्रोग्राम यह पता लगाने के लिए कि क्रमबद्ध रूप में स्ट्रिंग को ऑर्डर करने के लिए कितने वर्णों को पुनर्व्यवस्थित किया जाना चाहिए

मान लीजिए कि हमारे पास n वर्णों के साथ एक स्ट्रिंग S है। S में केवल लोअरकेस अक्षर हैं। हमें 0 से n की श्रेणी में एक संख्या k का चयन करना चाहिए, फिर S से k वर्णों का चयन करें और उन्हें किसी भी क्रम में क्रमित करें। इस प्रक्रिया में, शेष वर्ण अपरिवर्तित रहेंगे। हम इस पूरे ऑपरेशन को ठीक एक बार करते हैं। हमें k का मान ज्ञात करना है, जिसके लिए S वर्णानुक्रम में क्रमबद्ध हो जाता है।

इसलिए, यदि इनपुट एस ="एसीडीबी" जैसा है, तो आउटपुट 3 होगा, क्योंकि 'ए' सही जगह पर है और शेष वर्णों को पुनर्व्यवस्थित किया जाना चाहिए।

कदम

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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"