Greedy string swaps when white||14 ms Beats 99.58%
Intuition\n Describe your first thoughts on how to solve this problem. \nGreedy string again like several questions in the last week.\n- 921. Minimum Add to Mak
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGreedy string again like several questions in the last week.\n- [921. Minimum Add to Make Parentheses Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/solutions/5888865/greedy-string-againbeats-100/)\n- [1963. Minimum Number of Swaps to Make the String Balanced](https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/solutions/5884212/greedy-string42-ms-beats-9957/)\n\nThe idea is quite easy. When encountering \'0\' at i, say the sequence  is like (i=6, black=5)\n```\n0111110 -> 0011111\n```\nall the black on the left side of `s[i]` should be moved to the right side of this white ball. It will take `black=5` swaps.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize `black=0`\n2. Set up `swap=0` as `long long`\n3. Transverse the string `s`\n4. If c==\'1\' the black ball increase `black` by 1; otherwise add `black` to `swap`\n5. The loop is through, return the answer `swap`\n# How to move like 0111110 -> 0011111? \nLet (x,y) denote the permutation of the balls at x & at y.\nThe moving process can be written as a product of permutations of adjacent places like\n```\n(5, 6) (5, 4) (4, 3) (3, 2) (2, 1)\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code||C++ 14 ms Beats 99.58%\n```cpp []\nclass Solution {\npublic:\n    long long minimumSteps(string& s) {\n        int black=0;\n        long long  swap=0;\n        for(char c: s){\n            (c==\'1\')?black++:swap+=black;\n        }\n        return swap;\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Python code\n```\nclass Solution:\n    def minimumSteps(self, s: str) -> int:\n        black, swap=0, 0\n        for c in s:\n            if c==\'1\': black+=1\n            else: swap+=black\n        return swap\n        \n```
['String', 'Greedy', 'C++', 'Python3']