LeetCode Hard: Special Binary String

This is one Hard category problem on LeetCode.

A few things to observe in this problem are :

1. Treating a special binary string as a string with 1 corresponding to char ‘(‘ and 0 to character ‘)’ reduces it to a valid string of properly closed parentheses.
2. The first character of special binary strings (like the input string) has to be a 1, and the last character, a 0.
3. The special binary string can be a concatenation of only special binary strings.

Keeping these factsin mind, here is my recursive solution to the same:

 

class Solution {
    public String makeLargestSpecial(String S) {
        
        ArrayList res = new ArrayList<>();
        
        int count = 0, st = 0;
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '1')
                count++;
            else
                count--;
            if (count == 0) {
                res.add('1' + makeLargestSpecial(S.substring(st+1, i)) + '0');
                st = i+1;
            }
        }
        
        Collections.sort(res, Collections.reverseOrder());
        return String.join("", res);
        
    }
}

Let me know your thouhts in the comments below.

 

Happy Coding!