LeetCode 3499: Maximise Active Section with Trade
O(n) Time | O(1) Space | C++
You're given a binary string where 1 represents an active section and 0 represents an inactive one. You get exactly one trade:
Erase a block of
1s that has0s on both sides.Fill a block of
0s that has1s on both sides.
The goal is to maximise the final number of active sections.
At first glance, the problem encourages you to think about flipping individual bits. That quickly becomes messy. The trick is to change the unit of thinking and instead look at runs of consecutive 1s and 0s.
The first solution explicitly uses Run Length Encoding (RLE) to represent those runs. The second builds on the same idea but processes the runs as they are encountered, reducing the extra space to O(1).
The problem also pads the string as:
t = "1" + s + "1";
This handles the boundaries for free. Any 1 block touching either end of the original string becomes connected to the padded 1, so it only has a 0 on one side and can never be erased. Every remaining 1 run is therefore a valid candidate.
Observation
Suppose we erase a valid 1 block.
The zero runs on its left and right immediately merge into a larger zero run. Since that merged run is now surrounded by 1s, it becomes exactly the block we fill in the second step.
Although the erased block briefly becomes 0, it is immediately restored to 1 when the merged zero run is filled, so its contribution never changes.
The only real gain comes from converting the two neighbouring zero runs into 1s.
That means every candidate block has a score of:
totalOnes + leftZeroRun + rightZeroRun
So the answer is simply:
answer = totalOnes + max(leftZeroRun + rightZeroRun)
taken over every valid 1 block.
If no valid block exists, the answer is simply totalOnes.
O(n) Time, O(n) Space Solution
class Solution {
public:
int maxActiveSectionsAfterTrade(string s) {
string t = "1" + s + "1";
vector<pair<char,int>> runs;
for (int i = 0; i < t.size();) {
int j = i;
while (j < t.size() && t[j] == t[i])
j++;
runs.push_back({t[i], j - i});
i = j;
}
int totalOnes = count(s.begin(), s.end(), '1');
int maxGain = 0;
for (int i = 1; i + 1 < runs.size(); i++) {
if (runs[i].first == '1') {
maxGain = max(maxGain,
runs[i - 1].second +
runs[i + 1].second);
}
}
return totalOnes + maxGain;
}
};
This solution explicitly builds the Run Length Encoding by storing every run as a (character, length) pair.
Since the first and last runs always contain the padded 1s, scanning from 1 to runs.size() - 2 automatically skips the boundary cases.
Every remaining 1 run already has a zero run on both sides, so scoring it is simply a matter of adding the lengths of its neighbouring zero runs.
Building the runs and scanning them both take linear time.
Complexity:
Time Complexity:
O(n)Space Complexity:
O(n)
O(n) Time, O(1) Space Solution
The previous solution only needs the current run and its immediate neighbours, so storing every run is unnecessary.
Instead, process the string one run at a time.
Every zero run is the right neighbour of one 1 block and the left neighbour of the next, so once a zero run ends we already have everything needed to score the previous block.
class Solution {
public:
int maxActiveSectionsAfterTrade(string s) {
int totalOnes = 0;
int prevZero = 0;
int curZeros = 0;
bool havePending = false;
int maxGain = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1') {
totalOnes++;
if (i == 0 || s[i - 1] == '0') {
if (i > 0) {
if (havePending) {
maxGain = max(maxGain,
prevZero + curZeros);
}
prevZero = curZeros;
havePending = true;
} else {
havePending = false;
}
curZeros = 0;
}
} else {
curZeros++;
}
}
if (!s.empty() && s.back() == '0' && havePending) {
maxGain = max(maxGain,
prevZero + curZeros);
}
return totalOnes + maxGain;
}
};
curZeros tracks the zero run currently being traversed.
When a new 1 block begins, that zero run has just ended, which means we now know the right neighbour of the previous block.
After scoring it, that same zero run immediately becomes the left neighbour of the next block.
If the string ends with 0s, the final pending block never gets scored inside the loop, so we handle that single case after the scan finishes.
Complexity:
Time Complexity:
O(n)Space Complexity:
O(1)
Edge Cases
One subtle detail is easy to miss.
The problem lets us erase one block and fill another, but it never says those two blocks have to be related.
Could erasing one block and filling a completely different zero run ever produce a better answer?
No.
If a zero run can already be filled independently, then it was already surrounded by 1s.
Filling it gains its length, but the erased block is permanently lost, so the net gain is:
size(zero run) - size(erased block)
Now erase one of that zero run's neighbouring 1 blocks instead.
The erased block is rebuilt as part of the fill operation, and you gain the original zero run plus the zero run on the other side.
That is always at least as good because nothing is permanently lost.
The only exception is when the string has exactly three runs:
111...000...111
Both 1 blocks touch the boundary, so neither can be erased.
There is no valid trade, which means the answer is simply the original number of 1s.
Conclusion
The key to this problem is changing how you look at the string.
Once you stop thinking about individual characters and start thinking in terms of runs, the trade becomes easy to score.
From there, the explicit Run Length Encoding solution is straightforward, and the O(1) solution naturally follows by processing those same runs on the fly.
