Minimum Number Of Swaps To Make The Binary String Alternating - Leetcode Solution

Problem:

Given a binary string s, return the minimum number of swaps to make the string alternating, i.e., every adjacent characters should be different.

Example 1:

Input: s = "1100" Output: 1 Explanation: Swap s[1] with s[2], then s becomes "1010".

Example 2:

Input: s = "1111" Output: -1 Explanation: The string cannot be converted to a any alternating string.

Example 3:

Input: s = "010" Output: 0 Explanation: The string is already alternating.

Solution:

1. First, we count the number of 0's and 1's in the binary string.

2. We then check if the difference between the count of 0's and 1's is greater than 1. If it is, then we cannot make the string alternating by swapping and we return -1.

3. If the count of 0's and 1's is equal, we can start with either '0' or '1'. If it is not equal, and count of 0's is greater than count of 1's or vice versa, we start with the character that occurs fewer times.

4. We then initialize two variables, "ans1" and "ans2" to zero, which will store the number of swaps required to make the string alternating starting with '0' and '1' respectively. We then iterate over the string s and check the following conditions for each character:

• If the current character is equal to the expected character for the string to be alternating starting with '0', then we increment "ans1". Expected character will be '0' for even positions and '1' for odd positions.
• If the current character is equal to the expected character for the string to be alternating starting with '1', then we increment "ans2". Expected character will be '1' for even positions and '0' for odd positions.

5. We return the minimum value of "ans1" and "ans2".

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the binary string.

Space Complexity:

The space complexity of this solution is O(1), since we are using only a few extra variables to store the results.

1