hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Flip String to Monotone Increasing
Problem: Flip String to Monotone Increasing
Problem Link: leetcode.com/problems/flip-string-to-monotone-increasing/
Companies Asked: Google, Amazon, Microsoft
Approach:
Well, the intuition behind this solving this problem is to keep (not move/shift) all the 1s on the right side of the string, and all the 0s on the left side of the string so that it becomes monotonic increasing like 00011111.
So, for the ith position of the given string, either it will be 0 or it will be 1.
For the ith index to be monotonically increasing the string from 0 to (i - 1) should also be monotonically increasing.
Starting from index = 0, our choice should be converting tail-end 0s to 1 and front-end 1s to 0 at minimum cost.
There will be two states which are constantly changing.
One is position/index.
The other is 0/1 for each index.
As we are moving forward through the indices from 0 to N-1, we need to decide if the ith position deserves a 1 or a 0 based on the results of the (i - 1)th index. So overlapping sub-problem.
So that is a Dynamic Programming problem with two states, an index, and a value at each index.
If the (i - 1)th index is a 1, then our target will be making the ith index 1 as we are moving in the right direction.
If the current index's value is 0, we need 1 flip to make the current index's value 1.
We will be adding 1. Then we will be waiting for the result that will be achieved from the next part (i + 1) of the string.
If the (i - 1)th index is 0, then our target will be choosing between 0 and 1 based on the minimum flip counts that will be achieved between them. While choosing between 0 or 1,
If the ith index is 0, we do not need to add 1 extra flip count as we would like to keep the current index 0.
If the ith index is 1, we need to add 1 extra flip count as we would like to flip the current index 0.
If the ith index is 0, we need to add 1 extra flip count as we would like to flip the current index 1.
If the ith index is 1, we do not need to add 1 extra flip count as we would like to keep the current index 1.
Then we will be waiting for the result that will be achieved from the next part (i + 1) of the string.
After each call, return the value for each state (position, value_at_each_position).
At the end return the value of DP[0][0].
Time and Space Complexity:
Time Complexity: O(N) ( Most Optimized )
Space Complexity: O(1) (Most Optimized )
Code [C++] [DP + Memoization | O(N) & O(N)]
class Solution {
public:
int solve(int pos, int last, string & s, vector<vector<int>> & dp, int n){
if(pos >= n) return 0;
if(dp[pos][last] != -1) return dp[pos][last];
if(last == 1){
dp[pos][last] = (s[pos] == '0') + solve(pos+1, 1, s, dp, n);
}
else{
dp[pos][last] = (s[pos] == '0') + solve(pos+1, 1, s, dp, n);
dp[pos][last] = min(dp[pos][last], (s[pos] == '1') + solve(pos+1, 0, s, dp, n));
}
return dp[pos][last];
}
int minFlipsMonoIncr(string s) {
int n = s.size();
vector<vector<int>>dp(n, vector<int>(2, -1));
return solve(0, 0, s, dp, n);
}
};
Code [C++] [DP + Tabulation| O(N) & O(N)]
class Solution {
public:
int minFlipsMonoIncr(string s) {
int n = s.size();
vector<vector<int>>dp(n+1, vector<int>(2, 0));
for(int pos=n-1; pos>=0; pos--){
for(int last=1; last>=0; last--){
if(last == 1){
dp[pos][last] = (s[pos] == '0') + dp[pos+1][last];
}
else{
dp[pos][last] = (s[pos] == '0') + dp[pos+1][1];
dp[pos][last] = min(dp[pos][last], (s[pos] == '1') + dp[pos+1][0]);
}
}
}
return dp[0][0];
}
};
Code [C++] [DP + Space Optimization| O(N) & O(1)]
class Solution {
public:
int minFlipsMonoIncr(string s) {
int n = s.size();
// vector<vector<int>>dp(n+1, vector<int>(2, 0));
int cur_one = 0, cur_zero = 0, next_one = 0, next_zero = 0;
for(int pos=n-1; pos>=0; pos--){
for(int last=1; last>=0; last--){
if(last == 1){
cur_one = (s[pos] == '0') + next_one;
}
else{
cur_zero = (s[pos] == '0') + next_one;
cur_zero = min(cur_zero, (s[pos] == '1') + next_zero);
}
}
next_zero = cur_zero;
next_one = cur_one;
}
return next_zero;
}
};