Minimum Binary Swaps to a Palindrome
AT&T● MediumFULLTIMEOAProblem statement
You may swap the bits at any two positions containing different bits in the binary string s. The positions do not need to be adjacent.
Return the minimum number of swaps needed to make s a palindrome. Return -1 if no sequence of swaps can do so.
Function
minPalindromeSwaps(s: String) → intExamples
Example 1
s = "0100101"return = 2Using zero-based indices, swap positions0 and1 to get1000101, then positions3 and4 to get1001001. The result is a palindrome. Initially three symmetric pairs mismatch; a swap can fix at most two, so one swap cannot suffice.
Example 2
s = "101000"return = 1Swap positions0 and3 to get001100, which is a palindrome. The original string is not a palindrome, so one swap is minimal.
Constraints
- 1 <= s.length <= 200000.
- s contains only the characters 0 and 1.