重複刪除子字串“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)，空間複雜度為常數。