力扣 761. 特殊的二进制序列

题目来源：https://leetcode.cn/problems/special-binary-string/

大致题意：
给定一个特殊的二进制字符串，该字符串需要满足以下条件：

• 字符串所有前缀中，1 的数量不小于 0 的数量
• 字符串中 1 和 0 的数量相同

该字符串可以分割成具有上述属性的子串，可以将不同的子串交换位置，最后返回满足条件的字典序最大的特殊字符串

思路

对于长度为 2 的串，那么其字典序最大的特殊字符串为 10

对于长度为 4 的串，其字典序最大的特殊字符串为 1100，而这样的限制条件是原字符串本身即为 1100，若其为 1010，则只能交换其子串 10、10，无法变成 1100

举个例子，对于字符串 101100，其字典序最大的特殊字符串为 110010，其实就是分割成两个特殊子串 10 与 1100，然后将他们两个交换，具体操作时，即可以将当前字符串的特殊子串（此时假设该子串已经处理为字典序最大）放入集合中进行降序排序，最终拼接集合中的子串即为字典序最大的特殊子串

所以该题的解题思路可以概括为：

1. 将字符串分割成特殊子串，递归的将子串处理为字典序最大，处理后放入子串集合
2. 将子串集合降序排序并拼接

分割子串时，可以使用双指针遍历

• 左指针表示当前子串左侧位置，使用一个 sum 统计当前子串中 1 与 0 的个数（遇到 1 就 +1，遇到 0 就 -1），若 sum 为 0（即 1 与 0 个数相同），则表示左指针到当前位置可以分割为一个特殊子串，分割并更新左指针
• 由于会出现 11011000 的情况，即无法将字符串分割为几个有效特殊子串，而字符串内部可以分割（101100 可以分割），所以每次统计到 sum 为 0 时，都递归处理当前子串去掉首尾 1 和 0 的子串（一个有效的特殊子串首部一定为 1，尾部一定为 0）

代码：

class Solution {
    public String makeLargestSpecial(String s) {
    	// 字符串小于等于 2，直接返回
        if (s.length() <= 2) {
            return s;
        }
        // 子串集合
        List<String> subStr = new ArrayList<>();
        int n = s.length();
        // 左指针
        int left = 0;
        // 统计 1 和 0 出现的次数
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                sum++;
            } else {
                sum--;
            }
            // sum 为 0，表示左指针到当前位置出现的 1 和 0 数量相同，分割子串
            if (sum == 0) {
            	// 分割并递归处理子串为字典序最大
                subStr.add("1" + makeLargestSpecial(s.substring(left + 1, i)) + "0");
                // 更新左指针
                left = i + 1;
            }
        }
        // 降序排序
        Collections.sort(subStr, (a, b) -> b.compareTo(a));
        StringBuffer sb = new StringBuffer();
        // 拼接
        for (String str : subStr) {
            sb.append(str);
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37