DDSA Solutions

3499. Maximize Active Section with Trade I

MediumView on LeetCode
StringGreedyTwo Pointers

Problem Overview

Treat the string as augmented with outer 1s.

Intuition

Treat the string as augmented with outer 1s. One trade first turns a surrounded block of 1s into 0s, then turns a surrounded block of 0s into 1s. That is equivalent to picking two consecutive zero-runs (with 1s between them) and activating both — net gain equals the sum of their lengths. So count all existing 1s, then add the best adjacent zero-pair length.

Algorithm

  1. 1Scan s in runs of equal characters (two pointers per run).
  2. 2For each run of 1s, add its length to totalOnes.
  3. 3For each run of 0s with length cur, update mx = max(mx, pre + cur) and set pre = cur.
  4. 4Initialize pre to −∞ so the first zero run does not pair with nothing.
  5. 5Return totalOnes + mx (mx stays 0 when there is no pair of zero runs).

Example Walkthrough

Input: s = "0100"

  1. 1.Runs: 0 (len 1), 1 (len 1), 00 (len 2). totalOnes = 1.
  2. 2.First zero run: mx = max(0, −∞ + 1) = 1, pre = 1.
  3. 3.Second zero run: mx = max(1, 1 + 2) = 3.
  4. 4.Answer = 1 + 3 = 4 active sections.

Output: 4

Common Pitfalls

  • •The trade needs two adjacent zero segments — a single long zero run cannot be split for this gain.
  • •Initialize previous zero length to −∞ (or similar) so the first zero run does not falsely pair.
  • •Do not subtract the middle 1-run manually — the formula totalOnes + mx already accounts for the optimal trade.
  • •mx = 0 is correct when no two zero runs exist; do not force a trade.
3499.cs
C#


public class Solution
{
    // Approach: One optimal trade adds the longest pair of adjacent zero-runs (two
    // consecutive '0' segments separated by '1's). Scan runs of equal characters;
    // count all '1's, and track max(prevZeroRun + curZeroRun) over zero segments.
    // Answer = totalOnes + that maximum (0 if no valid pair).
    // Complexity: O(n) time and O(1) space.
    public int MaxActiveSectionsAfterTrade(string s)
    {
        int n = s.Length;
        int totalOnes = 0;  // Total count of '1's in the string
        int currentIndex = 0;
        int previousZeroSegmentLength = int.MinValue;  // Length of previous segment of '0's
        int maxZeroSegmentSum = 0;  // Maximum sum of two adjacent zero segments

        // Process the string by segments of consecutive identical characters
        while (currentIndex < n)
        {
            // Find the end of current segment with same character
            int segmentEnd = currentIndex + 1;
            while (segmentEnd < n && s[segmentEnd] == s[currentIndex])
            {
                segmentEnd++;
            }

            // Calculate current segment length
            int currentSegmentLength = segmentEnd - currentIndex;

            if (s[currentIndex] == '1')
            {
                // If current segment contains '1's, add to total count
                totalOnes += currentSegmentLength;
            }
            else
            {
                // If current segment contains '0's, update max possible trade value
                // We can potentially trade this segment with a '1' segment
                // Track the maximum sum of two adjacent '0' segments (separated by '1's)
                maxZeroSegmentSum = Math.Max(maxZeroSegmentSum,
                                            previousZeroSegmentLength + currentSegmentLength);
                previousZeroSegmentLength = currentSegmentLength;
            }

            // Move to next segment
            currentIndex = segmentEnd;
        }

        // Final answer: original '1's count plus the best possible trade
        totalOnes += maxZeroSegmentSum;
        return totalOnes;
    }
}
Was this solution helpful?

Related Problems