# 761. Special Binary String 特殊的二进制序列

## # 题目描述：

Special binary strings are binary strings with the following two properties:

• The number of 0's is equal to the number of 1's.
• Every prefix of the binary string has at least as many 1's as 0's.

Given a special string S, a move consists of choosing two consecutive, non-empty, special substrings of S, and swapping them. (Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.)

At the end of any number of moves, what is the lexicographically largest resulting string possible?

Example 1:

``````Input: S = "11011000"
Output: "11100100"
Explanation:
The strings "10" [occuring at S[1]] and "1100" [at S[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.
``````

Note:

1. S has length at most 50.
2. S is guaranteed to be a special binary string as defined above.

## # 题目大意

1. 字符串中0的个数等于1的个数
2. 这个字符串中任何前缀中1的个数不少于0的个数

## # 解题方法

``````class Solution(object):
def makeLargestSpecial(self, S):
"""
:type S: str
:rtype: str
"""
cnt = 0
res = list()
i= 0
for j, v in enumerate(S):
cnt += 1 if v == "1" else -1
if cnt == 0:
res.append("1" + self.makeLargestSpecial(S[i + 1:j]) + "0")
i = j + 1
return "".join(sorted(res, reverse=True))
``````

http://www.cnblogs.com/grandyang/p/8606024.html https://blog.csdn.net/u014688145/article/details/78996824 https://blog.csdn.net/BambooYH/article/details/80686074 http://www.cnblogs.com/zzuli2sjy/p/8260854.html

## # 日期

2018 年 10 月 2 日 —— 小蓝单车莫名其妙收了我1块钱，明明每个月免费骑10次的啊！