从二进制字符串提取0与1数量相等且分组连续的子串

问题说明 #

需要从二进制字符串中找出所有满足以下两个条件的连续子串：

• 子串中0和1的数量完全相等
• 子串中的0和1各自连续分组（即子串只能是连续1+连续0或连续0+连续1的结构，不存在0和1交替的情况）

示例 #

• 输入：1100110010
  输出："1100", "10", "0011", "01", "1100", "10", "01", "10"（与示例顺序不同但元素一致，可按需排序）
• 输入：1100
  输出："1100", "10"

原代码问题分析 #

原代码的逻辑是每次截取连续相同字符的块，然后判断该块内0和1的数量是否相等——这种思路完全错误：

1. 单一连续相同字符的块（如11或00）不可能满足0和1数量相等的条件
2. 完全忽略了跨连续块的连续子串（如1100中的10），也没有遍历所有可能的起始位置来检查符合结构的子串

正确解法思路 #

遍历所有可能的连续子串起始位置，逐个扩展结束位置，同时跟踪子串的结构和字符计数：

1. 对每个起始索引i，记录当前字符、该字符的计数、是否已经切换过字符（符合条件的子串只能有一次字符切换）
2. 扩展结束索引j时，若遇到相同字符则递增对应计数；若遇到不同字符则标记切换并开始计数另一字符
3. 若遇到第二次字符切换，说明子串结构不符合要求，直接终止当前起始位置的遍历
4. 每当两种字符的计数相等且已经切换过字符时，记录该子串

正确代码实现 #

string binaryString = "1100110010";
List<string> substrings = new List<string>();
int length = binaryString.Length;

for (int i = 0; i < length - 1; i++)
{
    char currentChar = binaryString[i];
    int count1 = 1;
    int count2 = 0;
    bool switched = false;

    for (int j = i + 1; j < length; j++)
    {
        if (binaryString[j] == currentChar)
        {
            count1++;
        }
        else
        {
            if (!switched)
            {
                switched = true;
                currentChar = binaryString[j];
                count2++;
            }
            else
            {
                // 出现第二次字符切换，结构不符合要求，终止循环
                break;
            }
        }

        // 满足条件：已切换过字符且两种字符数量相等
        if (switched && count1 == count2)
        {
            substrings.Add(binaryString.Substring(i, j - i + 1));
        }
    }
}

// 打印结果（可按需排序，比如按子串起始位置或长度）
foreach (string substring in substrings)
{
    Console.WriteLine(substring);
}

代码验证 #

• 对于输入1100，代码会输出"1100"和"10"，与示例2一致
• 对于输入1100110010，代码会收集到所有符合条件的子串，元素与示例1完全匹配

内容的提问来源于stack exchange，提问作者Thanushka