跳转至

761. 特殊的二进制字符串

题目描述

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

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

给定一个特殊的二进制字符串 s。

一次移动操作包括选择字符串 s 中的两个连续的、非空的、特殊子串，并交换它们。两个字符串是连续的，如果第一个字符串的最后一个字符与第二个字符串的第一个字符的索引相差正好为 1。

返回在字符串上应用任意次操作后可能得到的字典序最大的字符串。

 

示例 1:

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

示例 2：

输入：s = "10"
输出："10"

 

提示：

  • 1 <= s.length <= 50
  • s[i] 为 '0' 或 '1'。
  • s 是一个特殊的二进制字符串。

解法

方法一：递归 + 排序

我们可以把特殊的二进制序列看作“有效的括号”，其中 \(1\) 代表左括号，而 \(0\) 代表右括号。例如，"11011000" 可以看作："(()(()))"。

交换两个连续非空的特殊子串，相当于交换两个相邻的有效括号，我们可以使用递归来解决这个问题。

我们将字符串 \(s\) 中的每个“有效的括号”都看作一部分，递归处理，最后进行排序，得到最终答案。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(s\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        if s == '':
            return ''
        ans = []
        cnt = 0
        i = j = 0
        while i < len(s):
            cnt += 1 if s[i] == '1' else -1
            if cnt == 0:
                ans.append('1' + self.makeLargestSpecial(s[j + 1 : i]) + '0')
                j = i + 1
            i += 1
        ans.sort(reverse=True)
        return ''.join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String makeLargestSpecial(String s) {
        if ("".equals(s)) {
            return "";
        }
        List<String> ans = new ArrayList<>();
        int cnt = 0;
        for (int i = 0, j = 0; i < s.length(); ++i) {
            cnt += s.charAt(i) == '1' ? 1 : -1;
            if (cnt == 0) {
                String t = "1" + makeLargestSpecial(s.substring(j + 1, i)) + "0";
                ans.add(t);
                j = i + 1;
            }
        }
        ans.sort(Comparator.reverseOrder());
        return String.join("", ans);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s == "") {
            return s;
        }
        vector<string> ans;
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); ++i) {
            cnt += s[i] == '1' ? 1 : -1;
            if (cnt == 0) {
                ans.push_back("1" + makeLargestSpecial(s.substr(j + 1, i - j - 1)) + "0");
                j = i + 1;
            }
        }
        sort(ans.begin(), ans.end(), greater<string>{});
        return accumulate(ans.begin(), ans.end(), ""s);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func makeLargestSpecial(s string) string {
    if s == "" {
        return ""
    }
    ans := sort.StringSlice{}
    cnt := 0
    for i, j := 0, 0; i < len(s); i++ {
        if s[i] == '1' {
            cnt++
        } else {
            cnt--
        }
        if cnt == 0 {
            ans = append(ans, "1"+makeLargestSpecial(s[j+1:i])+"0")
            j = i + 1
        }
    }
    sort.Sort(sort.Reverse(ans))
    return strings.Join(ans, "")
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function makeLargestSpecial(s: string): string {
    if (s.length === 0) {
        return '';
    }

    const ans: string[] = [];
    let cnt = 0;

    for (let i = 0, j = 0; i < s.length; ++i) {
        cnt += s[i] === '1' ? 1 : -1;
        if (cnt === 0) {
            const t = '1' + makeLargestSpecial(s.substring(j + 1, i)) + '0';
            ans.push(t);
            j = i + 1;
        }
    }

    ans.sort((a, b) => b.localeCompare(a));
    return ans.join('');
}

评论