0761. Special Binary String¶
题目信息¶
- 题号:
0761
- 难度:
Hard
- 主题:
字符串、字典序、合法子串交换
- 原题:
- 重点:
特殊二进制串要求 0 与 1 数量相等且任意前缀中 1 不少于 0;一次操作只能交换两个连续、非空且各自特殊的子串,目标是得到字典序最大的可达字符串
题目重述¶
特殊二进制字符串同时满足两个条件:整个字符串中 0 与 1 的数量相等;从开头截取的任意前缀中,1 的数量都不少于 0 的数量。
给定一个保证为特殊二进制字符串的 s。一次操作可以选择其中两个首尾相接、均非空且各自也是特殊二进制字符串的子串,并交换这两个子串的位置。可以执行任意次操作,也可以不操作。
请返回所有可达结果中字典序最大的字符串。1 <= s.length <= 50,且 s 只包含字符 0 和 1。
自建示例¶
交换顶层的两个特殊子串:
输入:s = "10110100"
输出:"11010010"
解释:原串由连续特殊子串 "10" 和 "110100" 组成。交换二者得到 "11010010",使更长、以 "11" 开头的特殊子串位于前面;第二个子串内部已经不能通过合法交换得到更大的排列,因此该结果字典序最大。
无需交换:
输入:s = "111000"
输出:"111000"
解释:该字符串本身已经以三个 1 开头,任何合法交换都不能得到字典序更大的结果。