Problem:
Find the max length of consecutive ones with one flip (0 => 1)
Thinking process:
1. Naive method is to get all segments of 1s, at the same time keep this information: how many 0s are between two segments of 1s. Try to concatenate two segments with only one 0 between them. Update the max.
2. Cons: Many corner cases for this method (all 0s, all 1s, etc.). Two pass is proper, and O(N) space is needed. If with one pass, careful coding is needed with multiple if... else... statements.
3. If we want to know what is max length until current position, we are only interested in how many 0s we have encountered before. Since only one 0 is allowed. If we know the position of second last 0, things become clear.
4. Thus, keep a window [l, r] with at most one 0 in between. And the second last 0 is at position p = l - 1, so l = p + 1.
Follow up:
What if K (>=0) flips is allowed?
1. Then, we are interested in where the last K 0s are.
2. By using a queue to track the positions of previous 0s. If the size of queue is more than K, we need immediately remove the front of queue, let's say p, then l = p + 1.
3. In the code, I treat l as the previous slot of the window to get rid of +1 or -1.
4. Note that the queue technique can deal with input stream, if it is not a fixed vector.
5. But a long or long long or other big_integer is needed to track the ans, since it may be very large without MOD 1e9+7.
Find the max length of consecutive ones with one flip (0 => 1)
Thinking process:
1. Naive method is to get all segments of 1s, at the same time keep this information: how many 0s are between two segments of 1s. Try to concatenate two segments with only one 0 between them. Update the max.
2. Cons: Many corner cases for this method (all 0s, all 1s, etc.). Two pass is proper, and O(N) space is needed. If with one pass, careful coding is needed with multiple if... else... statements.
3. If we want to know what is max length until current position, we are only interested in how many 0s we have encountered before. Since only one 0 is allowed. If we know the position of second last 0, things become clear.
4. Thus, keep a window [l, r] with at most one 0 in between. And the second last 0 is at position p = l - 1, so l = p + 1.
Follow up:
What if K (>=0) flips is allowed?
1. Then, we are interested in where the last K 0s are.
2. By using a queue to track the positions of previous 0s. If the size of queue is more than K, we need immediately remove the front of queue, let's say p, then l = p + 1.
3. In the code, I treat l as the previous slot of the window to get rid of +1 or -1.
4. Note that the queue technique can deal with input stream, if it is not a fixed vector.
5. But a long or long long or other big_integer is needed to track the ans, since it may be very large without MOD 1e9+7.
No comments:
Post a Comment