通过删除具有替代字符的子序列将二进制字符串减少为空字符串

Question

这是在纳斯达克实习的编码回合中提出的一个问题。

程序说明：

该程序将一个二进制字符串作为输入。我们必须连续删除所有字符交替的子序列，直到字符串为空。任务是找到这样做所需的最少步骤数。

示例1：
让字符串为：0111001
Removed-0101, Remaining-110
Removed-10 , Remaining-1
Removed-1
No of steps = 3

Example2：
让字符串为：111000111
Removed-101, Remaining-110011
Removed-101, Remaining-101
Removed-101
No of steps = 3

示例3：
让字符串为：11011
Removed-101, Remaining-11
Removed-1 , Remaining-1
Removed-1
No of steps = 3

示例4：
让字符串为：10101
Removed-10101
No of steps = 1

我尝试的解决方案将二进制字符串的第一个字符视为我的子序列的第一个字符。然后创建一个新字符串，如果下一个字符不是交替序列的一部分，则将附加到该字符串中。新字符串成为我们的二进制字符串。这样，循环一直持续到新字符串为空。（有点 O(n^2) 算法）。正如预期的那样，它给了我一个超时错误。在 C++ 中添加了一些与我尝试过的 Java 代码类似的代码。

    #include<bits/stdc++.h>
    using namespace std;
    
    int main() {
        string str, newStr;
        int len;
        char c;
        int count = 0;
        getline(cin, str);
        len = str.length();
    
        //continue till string is empty
        while(len > 0) {
            len = 0;
            c = str[0];
            for(int i=1; str[i] != '\0';i++) {
                //if alternative characters are found, set as c and avoid that character
                if(c != str[i]) 
                    c = str[i];
                //if next character is not alternate, add the character to newStr
                else {
                    newStr.push_back(str[i]);
                    len++;
                }
            }
            str = newStr;
            newStr = "";
            count++;
        }
        cout<<count<<endl;
        return 0;
    }

我还尝试过寻找相同连续字符的最大子序列的长度等方法，但显然不能满足所有情况，例如example3。

希望有人可以帮助我为这个问题提供最优化的解决方案。最好是 C、C++ 或 python 中的代码。甚至算法也可以。

Answer 1

我们可以在O(n)时间和O(1)空间上解决这个问题。

这根本与秩序无关。当您考虑时，实际任务是如何将字符串划分为最少数量的由交替字符组成的子序列（允许单个字符）。只需维护两个队列或堆栈即可；一个代表 1，另一个代表 0，其中字符弹出其直接的替代前任。记录迭代过程中任意时刻队列的长度（不包括替换移动）。

例子：

(1)

0111001

   queues
1  1   -
0  -   0
0  -   00
1  1   0
1  11  -
1  111 -  <- max 3
0  11  0

对于O(1)空间，队列可以只是代表当前计数的两个数字。

(2)

111000111
   queues (count of 1s and count of 0s)
1  1  0
1  2  0
1  3  0  <- max 3
0  2  1
0  1  2
0  0  3  <- max 3
1  1  2
1  2  1
1  3  0  <- max 3

(3)

11011
   queues
1  1  0
1  2  0
0  1  1
1  2  0
1  3  0  <- max 3

(4)

10101

   queues
1  1  0  <- max 1
0  0  1  <- max 1
1  1  0  <- max 1
0  0  1  <- max 1
1  1  0  <- max 1