Welcome to Subscribe On Youtube
3501. Maximize Active Section with Trade II
Description
You are given a binary string s of length n, where:
'1'represents an active section.'0'represents an inactive section.
You can perform at most one trade to maximize the number of active sections in s. In a trade, you:
- Convert a contiguous block of
'1's that is surrounded by'0's to all'0's. - Afterward, convert a contiguous block of
'0's that is surrounded by'1's to all'1's.
Additionally, you are given a 2D array queries, where queries[i] = [li, ri] represents a substring s[li...ri].
For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[li...ri].
Return an array answer, where answer[i] is the result for queries[i].
Note
- For each query, treat
s[li...ri]as if it is augmented with a'1'at both ends, formingt = '1' + s[li...ri] + '1'. The augmented'1's do not contribute to the final count. - The queries are independent of each other.
Example 1:
Input: s = "01", queries = [[0,1]]
Output: [1]
Explanation:
Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.
Example 2:
Input: s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]
Output: [4,3,1,1]
Explanation:
-
Query
[0, 3]→ Substring"0100"→ Augmented to"101001"
Choose"0100", convert"0100"→"0000"→"1111".
The final string without augmentation is"1111". The maximum number of active sections is 4. -
Query
[0, 2]→ Substring"010"→ Augmented to"10101"
Choose"010", convert"010"→"000"→"111".
The final string without augmentation is"1110". The maximum number of active sections is 3. -
Query
[1, 3]→ Substring"100"→ Augmented to"11001"
Because there is no block of'1's surrounded by'0's, no valid trade is possible. The maximum number of active sections is 1. -
Query
[2, 3]→ Substring"00"→ Augmented to"1001"
Because there is no block of'1's surrounded by'0's, no valid trade is possible. The maximum number of active sections is 1.
Example 3:
Input: s = "1000100", queries = [[1,5],[0,6],[0,4]]
Output: [6,7,2]
Explanation:
-
Query
[1, 5]→ Substring"00010"→ Augmented to"1000101"
Choose"00010", convert"00010"→"00000"→"11111".
The final string without augmentation is"1111110". The maximum number of active sections is 6. -
Query
[0, 6]→ Substring"1000100"→ Augmented to"110001001"
Choose"000100", convert"000100"→"000000"→"111111".
The final string without augmentation is"1111111". The maximum number of active sections is 7. -
Query
[0, 4]→ Substring"10001"→ Augmented to"1100011"
Because there is no block of'1's surrounded by'0's, no valid trade is possible. The maximum number of active sections is 2.
Example 4:
Input: s = "01010", queries = [[0,3],[1,4],[1,3]]
Output: [4,4,2]
Explanation:
-
Query
[0, 3]→ Substring"0101"→ Augmented to"101011"
Choose"010", convert"010"→"000"→"111".
The final string without augmentation is"11110". The maximum number of active sections is 4. -
Query
[1, 4]→ Substring"1010"→ Augmented to"110101"
Choose"010", convert"010"→"000"→"111".
The final string without augmentation is"01111". The maximum number of active sections is 4. -
Query
[1, 3]→ Substring"101"→ Augmented to"11011"
Because there is no block of'1's surrounded by'0's, no valid trade is possible. The maximum number of active sections is 2.
Constraints:
1 <= n == s.length <= 1051 <= queries.length <= 105s[i]is either'0'or'1'.queries[i] = [li, ri]0 <= li <= ri < n
Solutions
Solution 1
-
impl Solution { pub fn max_active_sections_after_trade(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> { let bytes = s.as_bytes(); let length = bytes.len(); let total_ones = bytes.iter().filter(|byte| **byte == b'1').count() as i32; if !bytes.contains(&b'0') { return vec![total_ones; queries.len()]; } let mut zero_blocks: Vec<(usize, usize)> = Vec::new(); let mut zero_block_at_position = Vec::with_capacity(length); for index in 0..length { if bytes[index] == b'0' { if index > 0 && bytes[index - 1] == b'0' { zero_blocks.last_mut().unwrap().1 += 1; } else { zero_blocks.push((index, 1usize)); } } zero_block_at_position.push(zero_blocks.len() as isize - 1); } let zero_block_count = zero_blocks.len(); let adjacent_pair_count = zero_block_count.saturating_sub(1); let sparse_level_count = if adjacent_pair_count == 0 { 0 } else { usize::BITS as usize - adjacent_pair_count.leading_zeros() as usize }; let mut sparse_table = vec![0; adjacent_pair_count * sparse_level_count]; for pair_index in 0..adjacent_pair_count { sparse_table[pair_index] = (zero_blocks[pair_index].1 + zero_blocks[pair_index + 1].1) as i32; } for level in 1..sparse_level_count { let half_span = 1usize << (level - 1); let span = 1usize << level; for start in 0..=adjacent_pair_count - span { sparse_table[level * adjacent_pair_count + start] = sparse_table [(level - 1) * adjacent_pair_count + start] .max(sparse_table[(level - 1) * adjacent_pair_count + start + half_span]); } } let max_pair_sum = |left_pair: usize, right_pair: usize| -> i32 { let right_pair = right_pair.min(adjacent_pair_count - 1); if left_pair > right_pair { return 0; } let level = usize::BITS as usize - (right_pair - left_pair + 1).leading_zeros() as usize - 1; let span = 1usize << level; sparse_table[level * adjacent_pair_count + left_pair] .max(sparse_table[level * adjacent_pair_count + right_pair - span + 1]) }; queries .into_iter() .map(|query| { let left = query[0] as usize; let right = query[1] as usize; let left_block_index = zero_block_at_position[left]; let right_block_index = zero_block_at_position[right]; let left_zero_count = if left_block_index == -1 { -1 } else { let block_index = left_block_index as usize; zero_blocks[block_index].1 as i32 - (left - zero_blocks[block_index].0) as i32 }; let right_zero_count = if right_block_index == -1 { -1 } else { let block_index = right_block_index as usize; (right - zero_blocks[block_index].0 + 1) as i32 }; let first_internal_pair = left_block_index + 1; let last_internal_pair = (if bytes[right] == b'1' { right_block_index } else { right_block_index - 1 }) - 1; let last_full_zero_block = if bytes[right] == b'1' { right_block_index } else { right_block_index - 1 }; let mut best_total = total_ones; if bytes[left] == b'0' && bytes[right] == b'0' && left_block_index + 1 == right_block_index { best_total = best_total.max(total_ones + left_zero_count + right_zero_count); } else if first_internal_pair <= last_internal_pair { best_total = best_total.max( total_ones + max_pair_sum( first_internal_pair as usize, last_internal_pair as usize, ), ); } if bytes[left] == b'0' && left_block_index + 1 <= last_full_zero_block { best_total = best_total.max( total_ones + left_zero_count + zero_blocks[(left_block_index + 1) as usize].1 as i32, ); } if bytes[right] == b'0' && left_block_index < right_block_index - 1 { best_total = best_total.max( total_ones + right_zero_count + zero_blocks[(right_block_index - 1) as usize].1 as i32, ); } best_total }) .collect() } } -
class Solution { public List<Integer> maxActiveSectionsAfterTrade(String s, int[][] queries) { int n = s.length(); int active = 0; for (int i = 0; i < n; ++i) { if (s.charAt(i) == '1') { ++active; } } List<Integer> ans = new ArrayList<>(); if (s.indexOf('0') < 0) { for (int i = 0; i < queries.length; ++i) { ans.add(active); } return ans; } int[][] zeros = new int[n][2]; int z = 0; int[] idx = new int[n]; for (int i = 0; i < n; ++i) { if (s.charAt(i) == '0') { if (i > 0 && s.charAt(i - 1) == '0') { ++zeros[z - 1][1]; } else { zeros[z][0] = i; zeros[z++][1] = 1; } } idx[i] = z - 1; } int m = z - 1; int K = m > 0 ? 32 - Integer.numberOfLeadingZeros(m) : 0; int[][] st = new int[Math.max(K, 1)][Math.max(m, 0)]; for (int i = 0; i < m; ++i) { st[0][i] = zeros[i][1] + zeros[i + 1][1]; } for (int k = 1; k < K; ++k) { for (int i = 0; i + (1 << k) <= m; ++i) { st[k][i] = Math.max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]); } } for (int[] q : queries) { int L = q[0], R = q[1]; int iL = idx[L], iR = idx[R]; int cntL = iL < 0 ? -1 : zeros[iL][1] - (L - zeros[iL][0]); int cntR = iR < 0 ? -1 : R - zeros[iR][0] + 1; int start = iL + 1; int end = iR - (s.charAt(R) == '0' ? 1 : 0); int best = active; if (start < end) { best = Math.max(best, active + query(st, m, start, end - 1)); } if (s.charAt(L) == '0' && s.charAt(R) == '0' && iL + 1 == iR) { best = Math.max(best, active + cntL + cntR); } if (s.charAt(L) == '0' && iL + 1 < iR + (s.charAt(R) == '1' ? 1 : 0)) { best = Math.max(best, active + cntL + zeros[iL + 1][1]); } if (s.charAt(R) == '0' && iL < iR - 1) { best = Math.max(best, active + cntR + zeros[iR - 1][1]); } ans.add(best); } return ans; } private int query(int[][] st, int m, int l, int r) { if (l > r || m <= 0) { return 0; } int k = 31 - Integer.numberOfLeadingZeros(r - l + 1); return Math.max(st[k][l], st[k][r - (1 << k) + 1]); } } -
class Solution { public: vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) { int n = s.size(); int active = count(s.begin(), s.end(), '1'); if (s.find('0') == string::npos) { return vector<int>(queries.size(), active); } vector<pair<int, int>> zeros; vector<int> idx(n); for (int i = 0; i < n; ++i) { if (s[i] == '0') { if (i && s[i - 1] == '0') { ++zeros.back().second; } else { zeros.emplace_back(i, 1); } } idx[i] = (int) zeros.size() - 1; } int m = (int) zeros.size() - 1; int K = m ? 32 - __builtin_clz(m) : 0; vector<vector<int>> st(max(K, 1), vector<int>(max(m, 0))); for (int i = 0; i < m; ++i) { st[0][i] = zeros[i].second + zeros[i + 1].second; } for (int k = 1; k < K; ++k) { for (int i = 0; i + (1 << k) <= m; ++i) { st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]); } } auto query = [&](int l, int r) { if (l > r || m <= 0) { return 0; } int k = 31 - __builtin_clz(r - l + 1); return max(st[k][l], st[k][r - (1 << k) + 1]); }; vector<int> ans; ans.reserve(queries.size()); for (auto& q : queries) { int L = q[0], R = q[1]; int iL = idx[L], iR = idx[R]; int cntL = iL < 0 ? -1 : zeros[iL].second - (L - zeros[iL].first); int cntR = iR < 0 ? -1 : R - zeros[iR].first + 1; int start = iL + 1; int end = iR - (s[R] == '0'); int best = active; if (start < end) { best = max(best, active + query(start, end - 1)); } if (s[L] == '0' && s[R] == '0' && iL + 1 == iR) { best = max(best, active + cntL + cntR); } if (s[L] == '0' && iL + 1 < iR + (s[R] == '1')) { best = max(best, active + cntL + zeros[iL + 1].second); } if (s[R] == '0' && iL < iR - 1) { best = max(best, active + cntR + zeros[iR - 1].second); } ans.push_back(best); } return ans; } }; -
class Solution: def maxActiveSectionsAfterTrade( self, s: str, queries: List[List[int]] ) -> List[int]: n = len(s) active = s.count('1') if '0' not in s: return [active] * len(queries) zeros = [] idx = [0] * n for i in range(n): if s[i] == '0': if i and s[i - 1] == '0': zeros[-1][1] += 1 else: zeros.append([i, 1]) idx[i] = len(zeros) - 1 m = len(zeros) - 1 K = m.bit_length() if m else 0 st = [[0] * max(m, 0) for _ in range(max(K, 1))] for i in range(m): st[0][i] = zeros[i][1] + zeros[i + 1][1] for k in range(1, K): for i in range(m - (1 << k) + 1): st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]) def query(l: int, r: int) -> int: if l > r or m <= 0: return 0 k = (r - l + 1).bit_length() - 1 return max(st[k][l], st[k][r - (1 << k) + 1]) ans = [] for L, R in queries: iL, iR = idx[L], idx[R] cntL = -1 if iL < 0 else zeros[iL][1] - (L - zeros[iL][0]) cntR = -1 if iR < 0 else R - zeros[iR][0] + 1 start = iL + 1 end = iR - (s[R] == '0') best = active if start < end: best = max(best, active + query(start, end - 1)) if s[L] == '0' and s[R] == '0' and iL + 1 == iR: best = max(best, active + cntL + cntR) if s[L] == '0' and iL + 1 < iR + (s[R] == '1'): best = max(best, active + cntL + zeros[iL + 1][1]) if s[R] == '0' and iL < iR - 1: best = max(best, active + cntR + zeros[iR - 1][1]) ans.append(best) return ans -
func maxActiveSectionsAfterTrade(s string, queries [][]int) []int { n := len(s) active := 0 for i := 0; i < n; i++ { if s[i] == '1' { active++ } } if strings.IndexByte(s, '0') < 0 { ans := make([]int, len(queries)) for i := range ans { ans[i] = active } return ans } zeros := make([][2]int, 0, n) idx := make([]int, n) for i := 0; i < n; i++ { if s[i] == '0' { if i > 0 && s[i-1] == '0' { zeros[len(zeros)-1][1]++ } else { zeros = append(zeros, [2]int{i, 1}) } } idx[i] = len(zeros) - 1 } m := len(zeros) - 1 K := 0 if m > 0 { K = bits.Len(uint(m)) } st := make([][]int, max(K, 1)) for k := range st { st[k] = make([]int, max(m, 0)) } for i := 0; i < m; i++ { st[0][i] = zeros[i][1] + zeros[i+1][1] } for k := 1; k < K; k++ { for i := 0; i+(1<<k) <= m; i++ { st[k][i] = max(st[k-1][i], st[k-1][i+(1<<(k-1))]) } } query := func(l, r int) int { if l > r || m <= 0 { return 0 } k := bits.Len(uint(r-l+1)) - 1 return max(st[k][l], st[k][r-(1<<k)+1]) } ans := make([]int, 0, len(queries)) for _, q := range queries { L, R := q[0], q[1] iL, iR := idx[L], idx[R] cntL, cntR := -1, -1 if iL >= 0 { cntL = zeros[iL][1] - (L - zeros[iL][0]) } if iR >= 0 { cntR = R - zeros[iR][0] + 1 } start := iL + 1 end := iR if s[R] == '0' { end-- } best := active if start < end { best = max(best, active+query(start, end-1)) } if s[L] == '0' && s[R] == '0' && iL+1 == iR { best = max(best, active+cntL+cntR) } add := 0 if s[R] == '1' { add = 1 } if s[L] == '0' && iL+1 < iR+add { best = max(best, active+cntL+zeros[iL+1][1]) } if s[R] == '0' && iL < iR-1 { best = max(best, active+cntR+zeros[iR-1][1]) } ans = append(ans, best) } return ans }