Solved this Question in 1d dp
Intuition\n Here i thought of dp because for test case "110" we cannot go back we need to know what happens in past so we need to thought of recursively.\nas wh
# Intuition\n Here i thought of dp because for test case "110" we cannot go back we need to know what happens in past so we need to thought of recursively.\nas when you approach greedily and u only maintain the position of current zeroes you make a mistake. We can solve in this way by seeing the cnt of zeroes , by coming up with our greedy algo. \n\n# Approach\n1. We will maintain a dp array , here dp[i] represents the minimum number of swaps needed upto index \n2. We will fill up the dp array by maintaining the count of bbc (black_ball cnt) and while encountering \'0\' we fill up the array.\n\n\n# Complexity\n- Time complexity:\nO(n) = single traversal\n\n- Space complexity:\nO(n) = only dp array\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long minimumSteps(string s) {\n        int n = s.size();\n        vector<long long> dp(n, 0); // dp[i] represents the minimum number of\n                                    // swaps needed up to index i\n\n        int black_balls_count = 0;\n\n        for (int i = 0; i < n; ++i) {\n            if (s[i] == \'1\') {\n\n                dp[i] = (i > 0) ? dp[i - 1] : 0;\n                black_balls_count++;\n            } else {\n                // If it\'s a white ball, we need to swap it past all previous\n                // black balls\n                dp[i] = (i > 0 ? dp[i - 1] : 0) + black_balls_count;\n            }\n        }\n\n        return dp[n - 1];\n    }\n};\n```\n![cat.jpeg](https://assets.leetcode.com/users/images/4a066e63-f834-4b7c-8571-54dcd9036774_1728970813.1630914.jpeg)\n\nGive up a thumbs up if you like solution!\n
['String', 'Dynamic Programming', 'Greedy', 'Recursion', 'C++']