重复删除子字符串“10”中的字符形成的字典序最小的字符串

---

字典序最小的字符串是指在一组字符串中，在字典序中首先出现的字符串称为字典序最小的字符串。我们将给定一个二进制字符串（仅包含两种不同类型的字符 0 和 1），并且我们可以从给定字符串中的任何子字符串“10”中删除字符“1”，任何次数或任何时间。我们必须通过应用此方法创建字典序字符串。

示例

输入 1

字符串 str = “1101010011”

输出：000011

解释 − 因为我们只能删除字符“1”，所以我们将删除所有出现在零之前的 1。我们可以删除位于第 1、3 和 5 个索引处的“1”，并将得到字符串“1000011”。现在，我们只能删除第 0 个索引处的 1。

输入 2

字符串 str = “0011”

输出：0011

解释 − 1 的右侧没有零，这意味着我们无法更新字符串。

朴素方法

在这种方法中，我们将遍历字符串并找到“10”的组合或找到此子字符串。

我们将创建一个字符串来存储新字符串，并将新的元素添加到其中。

我们将使用 for 循环遍历上一个字符串，并将所需的字符添加到新字符串中。

我们将维护一个变量来标记我们是否正在删除任何字符，因为如果字符串正在更改，则可能再次获得新的子字符串“10”。

我们将使用 while 循环来重复检查字符串。让我们看看代码 −

示例

#include <bits/stdc++.h>
using namespace std;
// function to get the lexicographically smallest string 
string lexSmall(string str){
   string ans = ""; // string to store the answer 
   bool flag = true; // variable to mark the changes done     
   while(flag){
      flag = false;
      int len = str.length(); // getting size of the string         
      for(int i=0; i<len; i++){
         if(str[i] == '0'){
            ans += str[i];
         }
         else if(i != len-1 && str[i+1] == '0'){
            // current index is 1 and next is 0
            // so skip this and mark the flat true 
            // indicating the change in the string 
            flag = true;
            continue;
         }
         else{
            ans += str[i];
         }
      }
      if(flag){
         str = ans;
         ans = "";
      }
   }
   return ans;
}
int main(){
   string str = "1101010011"; // given string     
   // calling the function to get the required string 
   cout<<"The smallest string after a certain number of changes is "<<lexSmall(str)<<endl;
   return 0;
}

输出

The smallest string after a certain number of changes is 000011

时间和空间复杂度

上述代码的时间复杂度为 O(N*N)，其中 N 是给定字符串的长度。

上述代码的空间复杂度为 O(N)，因为我们将当前字符串传递给函数。

高效方法

在之前的方法中，我们每次都在更改字符串，这导致我们在每次迭代中都乘以 N。

我们可以通过一般的观察来优化结果，即如果存在一个零，它将删除其左侧的任何 1，并且在更新后，如果再次出现任何 1，它将再次删除它。

这意味着在从最后一个零出现后的字符串中，所有 1 都将消失。

我们将简单地使用 for 循环并从最后一个零开始检查，当我们从那里找到零时，我们将停止将 1 添加到答案字符串中，并且仅添加零之前的字符，在此之前我们将添加零和 1。

示例

#include <bits/stdc++.h>
using namespace std;
// function to get the lexicographically smallest string 
string lexSmall(string& str){
   string ans = ""; // string to store the answer 
   bool flag = false; // variable to mark the zero
   int len = str.length(); // getting length of the string     
   for(int i=len-1 ; i >= 0; i--){
      if(str[i] == '0'){
         ans += str[i];
         flag = true;
      }
      else if(flag){
         // flag is true means earlier there is a zero present 
         // so, no need to add this current character 
         continue;
      }
      else{
         ans += str[i];
      }
   }
   // reversing the current string 
   reverse(ans.begin(), ans.end());    
   return ans;
}
int main(){
   string str = "1101010011"; // given string     
   // calling the function to get the required string 
   cout<<"The smallest string after a certain number of changes is "<<lexSmall(str)<<endl;
   return 0;
}

输出

The smallest string after a certain number of changes is 000011

时间和空间复杂度

上述代码的时间复杂度为 O(N)，因为我们只遍历字符串一次，然后反转一次。

上述代码的空间复杂度为 O(1)，因为我们在这里没有使用任何额外的空间。

结论

在上面的教程中，我们学习了如何通过删除字符“1”（如果给定字符串中存在子字符串“10”）来找到给定字符串的字典序最小的字符串。我们实现了两种方法，第一种方法的时间复杂度为 O(N*N)，并具有额外的线性空间。第二种方法是最佳方法，时间复杂度为 O(N)，空间复杂度为常数。