Skip to content

3499. Maximize Active Section with Trade I

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <ranges>

class Solution {
 public:
  int maxActiveSectionsAfterTrade(string s) {
    vector<int> zeroGroupLengths;
    int maxZeroMerge = 0;

    for (int i = 0; i < s.length(); ++i)
      if (s[i] == '0') {
        if (i > 0 && s[i - 1] == '0')
          ++zeroGroupLengths.back();
        else
          zeroGroupLengths.push_back(1);
      }

    for (const auto& [a, b] : zeroGroupLengths | views::pairwise)
      maxZeroMerge = max(maxZeroMerge, a + b);

    return ranges::count(s, '1') + maxZeroMerge;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int maxActiveSectionsAfterTrade(String s) {
    List<Integer> zeroGroupLengths = new ArrayList<>();
    int maxZeroMerge = 0;

    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == '0') {
        if (i > 0 && s.charAt(i - 1) == '0')
          zeroGroupLengths.set(zeroGroupLengths.size() - 1,
                               zeroGroupLengths.get(zeroGroupLengths.size() - 1) + 1);
        else
          zeroGroupLengths.add(1);
      }
    }

    for (int i = 0; i < zeroGroupLengths.size() - 1; ++i)
      maxZeroMerge = Math.max(maxZeroMerge, zeroGroupLengths.get(i) + zeroGroupLengths.get(i + 1));

    return (int) s.chars().filter(c -> c == '1').count() + maxZeroMerge;
  }
}

1
2
3
4
class Solution:
  def maxActiveSectionsAfterTrade(self, s: str) -> int:
    zeroGroups = [len(list(g)) for c, g in itertools.groupby(s) if c == '0']
    return s.count('1') + max(map(sum, pairwise(zeroGroups)), default=0)