Java | Greedy | Two Pointers explained
\nAfter some experimenting it\'s easy to notice that:\n1. 00 => 10\n2. 011...110 => 101...111\n\nIn fact, you see that we are actually considering pair of zeros
\nAfter some experimenting it\'s easy to notice that:\n1. 00 => 10\n2. 011...110 => 101...111\n\nIn fact, you see that we are actually considering pair of zeros with 0..N ones between them. 00->10 is the basic case, while 0[1..]0 needs more explanation.\n\nWhen we have 10 we can change it to 01, thus all we do is \'pushing\' right-side zero to the left, until it meets another left-side and eventually 00-> 10.\n\nFor example:\n~~~\n010 -> 001 => 101\n0110 -> 0101 -> 0011 => 1011\n...\n011110 -> 011101 -> 011011 -> 010111 -> 001111 => 101111.\n...\n~~~\n\nSee how right-side zero moves to the left until they meet. Then we change 00 -> 10.\n\nSo at the end we have two pointers (left and right) and do binary manipulations when both of them are \'0\'.\n\n~~~\nclass Solution {\n    public String maximumBinaryString(String binary) {\n        if (binary.length() == 0 || binary.length() == 1) return binary;\n\n        char[] result = binary.toCharArray();\n\n        int left = 0, right = 1;\n        while (right < result.length) {\n            if (result[left] == \'0\' && result[right] == \'0\') {\n                result[left] = \'1\';\n                // right becomes \'1\'\n                result[right] = \'1\';\n                // .. but \'00\' is a special case so we first change it to \'11\' and then to \'10\' when right == left + 1\n                result[left + 1] = \'0\';\n                left = left + 1;\n                right = right + 1;\n            } else if (result[left] == \'1\') {\n                left++;\n                right = left + 1;\n            } else {\n                right++;\n            }\n        }\n        \n        return String.valueOf(result);\n    }\n}\n~~~\n\nTime complexity : O(N) (we always move one or both pointers)\nSpace complexity : O(N) (if taking result into consideration; with mutable input type it would have been O(1))
[]