Longest Non-Decreasing Substring After Pair Swaps
Visa● MediumFULLTIMEOAProblem statement
You are given a binary string dataStream of even length. Divide it into fixed, consecutive two-character blocks starting at zero-based indices 0, 2, 4, ....
In one operation, choose two distinct even indices i and j and exchange the complete blocks that start at those indices:
- Swap
dataStream[i]withdataStream[j]. - Swap
dataStream[i + 1]withdataStream[j + 1].
The order of the two characters inside each block never changes. You may perform any number of operations, including zero.
Return the maximum possible length of a non-decreasing contiguous substring after these operations. A binary substring is non-decreasing when all its 0 characters appear before all its 1 characters; either kind of character may be absent. The selected substring may begin or end inside a block.
Function
longestNonDecreasingSubstring(dataStream: String) → intExamples
Example 1
dataStream = "110000"return = 6Starting from 110000, the source's sequence exchanges blocks at (0, 2), (0, 4), and (2, 4), producing 001100, 001100, and 000011. The entire final string is non-decreasing, so the maximum length is 6.
Example 2
dataStream = "10"return = 1There is only one block, so no swap is possible. Either single character is a non-decreasing substring, but 10 is not.
Example 3
dataStream = "1010001101"return = 8Reorder the blocks as 10 | 00 | 01 | 11 | 10. The substring starting at the second character and ending at the next-to-last character is 00001111, of length 8.
Constraints
2 <= dataStream.length() <= 2 * 10^5.- The length of
dataStreamis even. - Every character is
0or1.