Python | Greedy  Pattern
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def minimumSteps(self, s: str) -> int:\n        ones_positions = []  # Stor
[see the Successfully Accepted Submission](https://leetcode.com/problems/separate-black-and-white-balls/submissions/1422695870/?envType=daily-question&envId=2024-10-15)\n\n# Code\n```python3 []\nclass Solution:\n    def minimumSteps(self, s: str) -> int:\n        ones_positions = []  # Stores the indices of all \'1\'s\n        \n        # Collect the positions of all \'1\'s\n        for i, char in enumerate(s):\n            if char == \'1\':\n                ones_positions.append(i)\n        \n        # Calculate minimum swaps\n        min_steps = 0\n        total_ones = len(ones_positions)\n        \n        # For each \'1\', calculate how many steps it needs to move to its target\n        for i, pos in enumerate(ones_positions):\n            target_position = len(s) - total_ones + i  # The target position for this \'1\'\n            min_steps += target_position - pos  # Count how many swaps are needed\n        \n        return min_steps\n\n```\n\n# Plan\n\n1. Traverse the string and track the positions of all the \'1\'s.\n2. For each \'1\', calculate how many steps (adjacent swaps) it would take to move to its correct position if all the \'1\'s were grouped together at the end.\n3. We calculate the number of swaps based on the difference between the current position of each \'1\' and where it needs to go.\n\n# Step-by-Step Explanation\n\n- First, gather the indices of all \'1\'s in the string.\n- Then, compute where each \'1\' needs to go if all the \'1\'s were grouped together at the end of the string.\n- The number of swaps required to move a \'1\' from its current position to its target position is simply the difference in positions minus how many other \'1\'s would have already been moved before it (because moving a \'1\' closer to the right reduces the effective number of swaps for the next \'1\').\n\n# Explanation of the Code\n\n- `ones_positions` stores the indices of all \'1\'s.\n- We calculate where each \'1\' should be to minimize swaps. The target position for the `i`-th \'1\' is determined by `len(s) - total_ones + i`, because the last `total_ones` positions should be occupied by the \'1\'s.\n- The number of swaps for each \'1\' is the difference between its current position and its target position.\n\n# Time Complexity\n\n- **O(n)**, where `n` is the length of the string. We make one pass through the string to find the positions of all \'1\'s, and another pass to calculate the swaps.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']