[Python3/Java/C++/Go] Two Pointers + Greedy - Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. Initialization:\n\n-
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Initialization:**\n\n- `n` stores the length of the input string `s`.\n- `res` is initialized to 0 to store the count of steps.\n- `l` and `r` are initialized to `n - 1`, pointing to the last index of `s`.\n\n**2. Iteration:**\n\n- The `while` loop iterates from the last index of `s` to the beginning.\n- If the current character `s[l]` is \'1\', it means the current substring from `l` to `r` can be converted to \'1\'s by flipping the \'0\'s.\n    - The number of steps required is calculated as `r - l`, which is the length of the substring.\n    - `res` is updated by adding the calculated steps.\n    - `r` is decremented to move the right pointer to the previous \'1\'.\n- `l` is decremented to move to the previous character.\n\n**3. Return Value:**\n\n- The final value of `res` represents the minimum number of steps required to convert the entire string `s` into \'1\'s.\n\n**Explanation:**\n\nThe code effectively calculates the minimum number of steps by identifying the longest substring of consecutive \'1\'s at the end of the string and flipping the \'0\'s within that substring. The loop iterates backward, starting from the last index, to find the longest such substring. The number of steps is calculated based on the length of this substring.\n\n# Complexity\n- Time complexity: $$O(N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minimumSteps(self, s: str) -> int:\n        n, res = len(s), 0\n        l = r = n - 1\n        while l >= 0:\n            if s[l] == "1":\n                res += r - l\n                r -= 1\n            l -= 1\n        return res\n```\n```java []\nclass Solution {\n    public long minimumSteps(String s) {\n        int n = s.length();\n        long res = 0;\n        int l = n - 1, r = n - 1;\n\n        while (l >= 0) {\n            if (s.charAt(l) == \'1\') {\n                res += r - l;\n                r--;\n            }\n            l--;\n        }\n\n        return res;\n    }\n}\n```\n```c++ []\nclass Solution {\npublic:\n    long long minimumSteps(string s) {\n        int n = s.length();\n        long long res = 0;\n        int l = n - 1, r = n - 1;\n\n        while (l >= 0) {\n            if (s[l] == \'1\') {\n                res += r - l;\n                r--;\n            }\n            l--;\n        }\n\n        return res;\n    }\n};\n```\n```go []\nfunc minimumSteps(s string) int64 {\n    n := len(s)\n    res := int64(0)\n    l, r := n-1, n-1\n    for l >= 0 {\n        if s[l] == \'1\' {\n            res += int64(r - l)\n            r--\n        }\n        l--\n    }\n    return res\n}\n```
['Two Pointers', 'String', 'Greedy', 'C++', 'Java', 'Go', 'Python3']