761. Special Binary String
Approach
Divide and Conquer. Recursively split s into special substrings
(balanced by +1 for '1' and -1 for '0'). For each, recursively process the inner
part and wrap with '1...0'. Sort resulting strings descending and concatenate.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Recursion solves a problem by calling itself with a smaller sub-problem. Every recursive solution needs: a base case (to stop) and a recursive case (to reduce). Stack space is O(depth). Convert deep recursion to iteration with an explicit stack when stack overflow is a concern.
// Approach: Divide and Conquer. Recursively split s into special substrings
// (balanced by +1 for '1' and -1 for '0'). For each, recursively process the inner
// part and wrap with '1...0'. Sort resulting strings descending and concatenate.
// Time: O(n^2) Space: O(n)
public class Solution
{
public string MakeLargestSpecial(string s)
{
List<string> specials = new List<string>();
int count = 0;
for (int i = 0, j = 0; j < s.Length; ++j)
{
count += s[j] == '1' ? 1 : -1;
if (count == 0)
{
specials.Add("1" + MakeLargestSpecial(s.Substring(i + 1, j - i - 1)) + "0");
i = j + 1;
}
}
specials.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
return string.Concat(specials);
}
}