给你一个长度为 n
的二进制字符串 s
,其中:
'1'
表示一个 活跃 区域。'0'
表示一个 非活跃 区域。你最多可以进行一次 操作 来最大化 s
中活跃区间的数量。在一次操作中,你可以:
'0'
包围的连续 '1'
区域转换为全 '0'
。'1'
包围的连续 '0'
区域转换为全 '1'
。此外,你还有一个 二维数组 queries
,其中 queries[i] = [li, ri]
表示子字符串 s[li...ri]
。
对于每个查询,确定在对子字符串 s[li...ri]
进行最优交换后,字符串 s
中 可能的最大 活跃区间数。
返回一个数组 answer
,其中 answer[i]
是 queries[i]
的结果。
注意
s[li...ri]
处理时,将其看作是在两端都加上一个 '1'
后的字符串,形成 t = '1' + s[li...ri] + '1'
。这些额外的 '1'
不会对最终的活跃区间数有贡献。
示例 1:
输入: s = "01", queries = [[0,1]]
输出: [1]
解释:
因为没有被 '0'
包围的 '1'
区域,所以没有有效的操作可以进行。最大活跃区间数是 1。
示例 2:
输入: s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]
输出: [4,3,1,1]
解释:
查询 [0, 3]
→ 子字符串 "0100"
→ 变为 "101001"
选择 "0100"
,"0100"
→ "0000"
→ "1111"
。
最终字符串(去掉添加的 '1'
)为 "1111"
。最大活跃区间数为 4。
查询 [0, 2]
→ 子字符串 "010"
→ 变为 "10101"
选择 "010"
,"010"
→ "000"
→ "111"
。
最终字符串(去掉添加的 '1'
)为 "1110"
。最大活跃区间数为 3。
查询 [1, 3]
→ 子字符串 "100"
→ 变为 "11001"
因为没有被 '0'
包围的 '1'
区域,所以没有有效的操作可以进行。最大活跃区间数为 1。
查询 [2, 3]
→ 子字符串 "00"
→ 变为 "1001"
因为没有被 '0'
包围的 '1'
区域,所以没有有效的操作可以进行。最大活跃区间数为 1。
示例 3:
输入: s = "1000100", queries = [[1,5],[0,6],[0,4]]
输出: [6,7,2]
解释:
查询 [1, 5]
→ 子字符串 "00010"
→ 变为 "1000101"
选择 "00010"
,"00010"
→ "00000"
→ "11111"
。
最终字符串(去掉添加的 '1'
)为 "1111110"
。最大活跃区间数为 6。
查询 [0, 6]
→ 子字符串 "1000100"
→ 变为 "110001001"
选择 "000100"
,"000100"
→ "000000"
→ "111111"
。
最终字符串(去掉添加的 '1'
)为 "1111111"
。最大活跃区间数为 7。
查询 [0, 4]
→ 子字符串 "10001"
→ 变为 "1100011"
因为没有被 '0'
包围的 '1'
区域,所以没有有效的操作可以进行。最大活跃区间数为 2。
示例 4:
输入: s = "01010", queries = [[0,3],[1,4],[1,3]]
输出: [4,4,2]
解释:
查询 [0, 3]
→ 子字符串 "0101"
→ 变为 "101011"
选择 "010"
,"010"
→ "000"
→ "111"
。
最终字符串(去掉添加的 '1'
)为 "11110"
。最大活跃区间数为 4。
查询 [1, 4]
→ 子字符串 "1010"
→ 变为 "110101"
选择 "010"
,"010"
→ "000"
→ "111"
。
最终字符串(去掉添加的 '1'
)为 "01111"
。最大活跃区间数为 4。
查询 [1, 3]
→ 子字符串 "101"
→ 变为 "11011"
因为没有被 '0'
包围的 '1'
区域,所以没有有效的操作可以进行。最大活跃区间数为 2。
提示:
1 <= n == s.length <= 105
1 <= queries.length <= 105
s[i]
只有 '0'
或 '1'
。queries[i] = [li, ri]
0 <= li <= ri < n
ans[i] = len[i - 1] + len[i + 1]
, where i
is a one-segment.ans[i] = 0
.i - 1
, i
, and i + 1
) should be fully covered by the substring.