ソートされた形式で文字列を並べ替えるために再配置する必要がある文字数を見つけるC++プログラム

n文字の文字列Sがあるとします。 Sには小文字のみが含まれます。 0からnの範囲の数値kを選択してから、Sからk文字を選択し、それらを任意の順序で並べ替える必要があります。このプロセスでは、残りの文字は変更されません。この操作全体を1回だけ実行します。 Sがアルファベット順にソートされるkの値を見つける必要があります。

したがって、入力がS ="acdb"の場合、「a」は正しい場所にあり、残りの文字を再配置する必要があるため、出力は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"

出力

3