https://www.cnblogs.com/grandyang/p/8606024.html
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:
Shas length at most50.Sis guaranteed to be a special binary string as defined above.
https://leetcode.com/problems/special-binary-string/discuss/113211/JavaC%2B%2BPython-Easy-and-Concise-Recursion
Just 4 steps:
- Split S into several special strings (as many as possible).
- Special string starts with 1 and ends with 0. Recursion on the middle part.
- Sort all special strings in lexicographically largest order.
- Join and output all strings.
Update
The middle part of a special string may not be another special string. But in my recursion it is.
For example, 1M0 is a splitted special string. M is its middle part and it must be another special string.
For example, 1M0 is a splitted special string. M is its middle part and it must be another special string.
Because:
- The number of 0's is equal to the number of 1's in
M - If there is a prefix
PofMwhich has one less 1's than 0's,1Pwill make up a special string.1Pwill be found as special string before1M0in my solution.
It means that every prefix ofMhas at least as many 1's as 0's.
Based on 2 points above, M is a special string.
public String makeLargestSpecial(String S) {
int count = 0, i = 0;
List<String> res = new ArrayList<String>();
for (int j = 0; j < S.length(); ++j) {
if (S.charAt(j) == '1') count++;
else count--;
if (count == 0) {
res.add('1' + makeLargestSpecial(S.substring(i + 1, j)) + '0');
i = j + 1;
}
}
Collections.sort(res, Collections.reverseOrder());
return String.join("", res);
}
Logical Thinking
If we regard 1, 0 in the definition of the special string as '(' and ')' separately,
the problem is actually to get the string which is so-called valid parenthesis and meanwhile is the lexicographically largest.
It is intuitive that we prefer deeper valid parenthesis to sit in front (deeper means the string surrounded with more pairs of parenthesis, e.g., '(())' is deeper than '()' ). We can achieve that by sorting them reversely.
we go through
If we regard 1, 0 in the definition of the special string as '(' and ')' separately,
the problem is actually to get the string which is so-called valid parenthesis and meanwhile is the lexicographically largest.
It is intuitive that we prefer deeper valid parenthesis to sit in front (deeper means the string surrounded with more pairs of parenthesis, e.g., '(())' is deeper than '()' ). We can achieve that by sorting them reversely.
we go through
S. Whenever the parentheses we met can be balanced (i.e., balance == 0), we construct valid parentheses -- by putting (on the left boundary, )on the right boundary, and doing with the inner part following the same pattern.
Clear Java Code
public String makeLargestSpecial(String S) {
int balance = 0, l = 0;
List<String> subResults = new LinkedList<>();
for (int r = 0; r < S.length(); r++) {
if (S.charAt(r) == '0') {
balance--;
}
else {
balance++;
}
if (balance == 0) {
subResults.add("1" + makeLargestSpecial(S.substring(l + 1, r)) + "0");
l = r + 1;
}
}
Collections.sort(subResults, Collections.reverseOrder());
return String.join("", subResults);
}
According to the description , there are 2 requirement for
Special-String- 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.
The 2nd definition is essentially saying that at any point of the string, you cannot have more 0's than 1's.
If we map
A
'1' to '(', '0's to ')', a Special-String is essentially Valid-Parentheses, therefore share all the properties of a Valid-ParenthesesA
VP (Valid-Parentheses) have 2 form:- single nested
VPlike"(())", or"1100"; - a number of consecutive
sub-VPs like"()(())", or"101100", which contains"()" + "(())"or"10" + "1100"
And this problem is essentially ask you to reorder the
Answer is, by moving the 2nd sub-string to the front. Because deeply nested VP contains more consecutive
sub-VPs in a VP to make it bigger. If we look at this example : "()(())" or "101100", how would you make it bigger?Answer is, by moving the 2nd sub-string to the front. Because deeply nested VP contains more consecutive
'('s or '1's in the front. That will make reordered string bigger.
The above example is straitforward, and no recursion is needed. But, what if the groups of
Like if we put another
sub-VPs are not in the root level?Like if we put another
"()(())" inside "()(())", like "()(( ()(()) ))", in this case we will need to recursively reorder the children, make them MVP(Max-Valid-Parentheses), then reorder in root.
To summarize, we just need to reorder all groups of
VPs or SS's at each level to make them MVP, then reorder higher level VPs; string makeLargestSpecial(string s) {
int i = 0;
return dfs(s, i);
}
private:
string dfs(string& s, int& i) {
string res;
vector<string> toks;
while (i < s.size() && res.empty()) {
if (s[i++] == '1') toks.push_back(dfs(s, i));
else res += "1";
}
bool prefix = res.size();
sort(toks.begin(), toks.end());
for (auto it = toks.rbegin(); it != toks.rend(); it++) res += *it;
if (prefix) res += '0';
return res;
}
这道题给了我们一个特殊的二进制字符串，说是需要满足两个要求，一是0和1的个数要相等，二是任何一个前缀中的1的个数都要大于等于0的个数。根据压力山大大神的帖子，其实就是一个括号字符串啊。这里的1表示左括号，0表示右括号，那么题目中的两个限制条件其实就是限定这个括号字符串必须合法，即左右括号的个数必须相同，且左括号的个数随时都要大于等于右括号的个数，可以参见类似的题目Valid Parenthesis String。那么这道题让我们通过交换子字符串，生成字母顺序最大的特殊字符串，注意这里交换的子字符串也必须是特殊字符串，满足题目中给定的两个条件，换作括号来说就是交换的子括号字符串也必须是合法的。那么我们来想什么样的字符串是字母顺序最大的呢，根据题目中的例子可以分析得出，应该是1靠前的越多越好，那么换作括号来说就是括号嵌套多的应该放在前面。比如我们分析题目中的例子:
11011000 -> (()(()))
11100100 -> ((())())
我们发现，题目中的例子中的交换操作其实是将上面的红色部分和蓝色部分交换了，因为蓝色的部分嵌套的括号多，那么左括号就多，在前面的1就多，所以字母顺序大。所以我们要做的就是将中间的子串分别提取出来，然后排序，再放回即可。上面的这个例子相对简单一些，实际上上面的红色和蓝色部分完全可以更复杂，所以再给它们排序之前，其自身的顺序应该已经按字母顺序排好了才行，这种特点天然适合递归的思路，先递归到最里层，然后一层一层向外扩展，直至完成所有的排序。
好，下面我们来看递归函数的具体写法，由于我们移动的子字符串也必须是合法的，那么我们利用检测括号字符串合法性的一个最常用的方法，就是遇到左括号加1，遇到右括号-1，这样得到0的时候，就是一个合法的子字符串了。我们用变量i来统计这个合法子字符串的起始位置，字符串数组v来保存这些合法的子字符串。好了，我们开始遍历字符串S，遇到1，cnt自增1，否则自减1。当cnt为0时，我们将这个字串加入v，注意前面说过，我们需要给这个字串自身也排序，所以我们要对自身调用递归函数，我们不用对整个子串调用递归，因为字串的起始位置和结束位置是确定的，一定是1和0，我们只需对中间的调用递归即可，然后更新i为j+1。当我们将所有排序后的合法字串存入v中后，我们对v进行排序，将字母顺序大的放前面，最后将其连为一个字符串即可
