檢查是否可以透過最多將括號移動到任一端 K 次來獲得平衡括號

---

在這個問題中，我們需要檢查是否可以透過將字串中最多 K 個字元移動到字串末尾來獲得有效的平衡括號子序列。

為了解決這個問題，我們可以使用棧資料結構。解決問題的邏輯是，如果我們在'('（開括號）之前找到超過 K 個')'（閉括號），我們就無法將字串轉換為有效的子序列。

問題陳述 – 我們給定一個包含'('和')'括號序列的字串 str。字串的長度為 N。此外，我們給定一個正整數 K。我們需要檢查是否可以透過將字串中最多 K 個字元移動到字串末尾來使給定字串成為有效的括號子序列。根據我們是否可以生成有效的子序列，列印'Yes'或'No'。

示例

輸入– str = ")()()(", k = 1

輸出– 'Yes'

說明– 將第一個字元移動到字串末尾後，我們可以得到'()()()'，這是一個有效的括號子序列。

輸入– str = "))())()(((", k = 2

輸出– No,

說明– 我們最多可以將 2 個字元移動到字串末尾。因此，將前 2 個字元移動到字串末尾後，我們可以得到'())()((())'，這不是一個有效的括號子序列。

輸入– str = ‘()(‘, k = 10

輸出– No

說明– 字串中開括號和閉括號的數量不相等，因此無法建立有效的括號子序列。

方法 1

在本方法中，我們將使用棧資料結構來解決問題。

演算法

• 如果 n 是奇數，則返回 false，因為如果字串長度是奇數，我們無法獲得平衡括號的子序列。

• 定義'open'和'close'變數，並初始化為零。

• 使用迴圈遍歷字串。如果當前字元是'('，則將 open 的值增加 1。否則，將')'的值增加 1。

• 如果 open 和 closed 不相等，則返回 false，因為如果開括號和閉括號的總數不相等，我們無法獲得平衡子序列。

• 將'res'變數初始化為零，並定義一個空棧。

• 再次開始遍歷字串。

• 如果當前字元是'('，則將其壓入棧中。

• 如果當前字元是')'，並且棧不為空，則從棧中刪除頂部元素。否則，將'res'的值增加 1，因為我們需要將字元移動到末尾。

• 最後，檢查'res'的值是否小於 K。如果是，則返回 true。否則，返回 false。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if it is possible to make the string balanced according to the given condition
bool getMinMoves(string s, int n, int k) {
   // If the length of the string is odd, it is not possible to make the string balanced
   if(n % 2 != 0) {
      return false;
   }
   // count the total number of opening and closing brackets
   int open = 0, close = 0;
   // Traverse the string
   for (int i = 0; i < n; i++) {
      // If the current character is opening a bracket, increment open. Else increment close
      if (s[i] == '(') {
          open++;
      } else {
          close++;
      }
   }
   // If the number of opening brackets is not equal to the number of closing brackets, it is not possible to make string balanced
   if (open != close) {
      return false;
   }
   // to store moves required to make string balanced
   int res = 0;
   // Defining the stack
   stack<char> st;
   // Traverse the string
   for (int i = 0; i < n; ++i) {
      // If the current character is opening the bracket, push to the stack
      if (s[i] == '(') {
          st.push(s[i]);
      } else {
          if(!st.empty()) {
            st.pop();
            } else {
                // Increment the res
                ++res;
            }
       }
   }
   // If res is less than or equal to k, then return true. Else return false
   if (res <= k) {
      return true;
   } else {
      return false;
   }
}
int main() {
   string str = "))())()(((";
   int K = 2;
   if (getMinMoves(str, str.length(), K)) {
      cout << "Yes, It is possible to make valid parenthesis by moving characters to either end at most K number of times";
   } else {
      cout << "No, It is not possible to make valid parenthesis by moving characters to either end at most K number of times";
   }
   return 0;
}

輸出

No, It is not possible to make valid parenthesis by moving characters to either end at most K number of times

時間複雜度 – O(N)，因為我們遍歷了字串。

空間複雜度 – O(N)，因為我們使用了棧。

方法 2

在本方法中，我們將編寫最佳化的程式碼，不使用棧來提高程式碼的空間複雜度。

演算法

• 如果字串長度是奇數，則返回 false。

• 使用 count() 方法計算'('和')'字元的總數。如果兩者的數量不相等，則返回 false。

• 定義'res'和'count'變數，並初始化為零。

• 開始遍歷字串

• 如果當前字元是'('，則將 count 的值增加 1。否則，將 count 的值減少 1。

• 如果'count'的值小於零，則將'res'的值增加 1，並將 count 更新為零。

• 迴圈迭代完成後，返回'res <= k'的值。

示例

#include <bits/stdc++.h>
using namespace std;
bool getMinMoves(string s, int n, int k) {
   // If the length of the string is odd, it is not possible to make the string balanced
   if(n % 2 != 0) {
      return false;
   }
   int open = 0, close = 0;
   // count the number of opening and closing brackets
   open = count(s.begin(), s.end(), '(');
   close = count(s.begin(), s.end(), ')');
   // If the number of opening brackets is not equal to the number of closing brackets, it is not possible to make string balanced
   if (open != close) {
      return false;
   }
   // to store moves required to make string balanced
   int res = 0;
   int count = 0;
   // Traverse the string
   for (int i = 0; i < n; ++i) {
      // If the current character is opening bracket, increment count by 1
      if (s[i] == '(') {
          ++count;
      } else {
          // Decrement count by 1
          --count;
          // If the count becomes negative, then update the count to 0 and increment res by 1.
          if (count < 0) {
              // Update the count
              count = 0;
              // Increment the res
              ++res;
          }
      }
   }
   return (res <= k);
}
int main() {
   string str = ")()()(";
   int K = 1;
   if (getMinMoves(str, str.length(), K)) {
      cout << "Yes, It is possible to make valid parenthesis by moving characters to either end at most K number of times";
   } else {
      cout << "No, It is not possible to make valid parenthesis by moving characters to either end at most K number of times";
   }
   return 0;
}

輸出

Yes, It is possible to make valid parenthesis by moving characters to either end at most K number of times

時間複雜度 – O(N)，因為我們遍歷了字串。

空間複雜度 – O(1)，因為我們沒有使用動態空間。