【2022-08-08每日一题】761. 特殊的二进制序列

2022-08-08每日一题：761. 特殊的二进制序列

难度：Hard

标签：递归 、 字符串

特殊的二进制序列是具有以下两个性质的二进制序列：

• 0 的数量与 1 的数量相等。
• 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

说明:

1. S 的长度不超过 50。
2. S 保证为一个满足上述定义的特殊 的二进制序列。

此题可以看成是有效的括号，将 1 看成左括号 (，0 看成右括号 )，比如，“1100” 可以看做是 “(())"，这样就比较好理解。也就是说最后我们需要通过一系列操作（有效的括号子串交换位置）之后让左括号尽量在右括号前面，比如，对于 “(()(()))"，我们可以把中间 “()” 和 “(())” 交换之后变成 “((())())"。

那么，代码就比较容易写了，我们可以遍历整个字符串，找到它的有效子串，再把这些子串降序排个序就完事了，当然，这里在找到这些子串之后，子串内部也可以使用相同的规则去做处理，所以，我们可以使用递归来搞。

func makeLargestSpecial(s string) string {
    if len(s) <= 2 {
        return s
    }
    subs := sort.StringSlice{}
    cnt, left := 0, 0
    for i, ch := range s {
        if ch == '1' {
            cnt++
        } else if cnt--; cnt == 0 {
            subs = append(subs, "1"+makeLargestSpecial(s[left+1:i])+"0")
            left = i + 1
        }
    }
    sort.Sort(sort.Reverse(subs))
    return strings.Join(subs, "")
}

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

LeetCode题库地址

• https://leetcode.cn/problems/special-binary-string