C ++中的特殊二进制字符串

假设我们有一个空间二进制字符串。该字符串具有以下几个属性-

• 0和1的数目相同

• 二进制字符串中的每个前缀至少有1到0

现在假设我们有特殊的字符串S，实际上是选择两个连续的非空的特殊S子字符串，然后交换它们。

在任何数量的移动结束时，我们都必须找到按字典顺序排列的最大结果字符串。

因此，如果输入类似于11011000，则输出将为11100100，这是因为：子字符串“ 10”和“ 1100”被交换了。在几次移动后，这是字典上可能出现的最大字符串。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数makeLargestSpecial()，它将花费s，

• ret：=空字符串

• 定义字符串数组v

• i：= 0

• 对于初始化j：= 0，cnt：= 0，当j <s的大小时，更新（j增加1），-

• 在v的末尾插入“ 1” + makeLargestSpecial（s的子字符串，从索引i +1到j-i-1）

• i：= j + 1

• （将cnt减1）

• （将cnt增加1）

• 如果s [j]与'1'相同，则-

• 除此以外

• 如果cnt与0相同，则-

• 排序数组vr

• 对于初始化i：= 0，当i <v的大小时，更新（将i增加1），执行-

• 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