检查是否可以通过最多将括号移动到任一端 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)，因为我们没有使用动态空间。