C++の特別なバイナリ文字列

• 0と1の数は同じです

• バイナリ文字列のすべてのプレフィックスには、少なくとも0と同じ数の1があります

ここで、特別な文字列Sがあるとします。移動とは、実際にはSの2つの連続した、空ではない特別な部分文字列を選択し、それらを交換することです。

任意の数の移動の最後に、辞書式順序で可能な最大の結果の文字列を見つける必要があります。

したがって、入力が11011000のような場合、出力は11100100になります。これは、次の理由によるものです。サブストリング「10」と「1100」が交換されます。これは、数回の移動で可能な辞書式順序で最大の文字列です。

これを解決するには、次の手順に従います-

• 関数makeLargestSpecial（）を定義します。これにはsがかかります

• ret：=空の文字列

• 文字列の配列vを定義する

• i：=0

• 初期化j：=0、cnt：=0の場合、j

  • s[j]が'1'と同じ場合、-

    • （cntを1増やします）

  • それ以外の場合

    • （cntを1減らします）

  • cntが0と同じ場合、-

    • vの最後に「1」+makeLargestSpecial（インデックスi +1からj--i-1までのsの部分文字列）を挿入します

    • i：=j + 1

• 配列v.rを並べ替える

• 初期化i：=0の場合、i

  • ret：=ret + v [i]

• retを返す

• メインメソッドから、文字列を使用してmakeLargestSpecial（）を呼び出します。

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string makeLargestSpecial(string s) {
      string ret = "";
      vector<string> v;
      int i = 0;
      for (int j = 0, cnt = 0; j < s.size(); j++) {
         if (s[j] == '1') {
            cnt++;
         }
         else
         cnt--;
         if (cnt == 0) {
            v.push_back("1" + makeLargestSpecial(s.substr(i + 1,
            j - i - 1)) + "0");
            i = j + 1;
         }
      }
      sort(v.rbegin(), v.rend());
      for (int i = 0; i < v.size(); i++)
      ret += v[i];
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.makeLargestSpecial("11011000"));
}

入力

11011000

出力

11100100