Minimum substring reversals required to make given Binary String alternating

0 0 5 minutes read

Given a binary string S of length N, the task is to count the minimum number substrings of S that is required to be reversed to make the string S alternating. If it is not possible to make string alternating, then print “-1”.

Examples:

Input: S = “10001110”
Output: 2
Explanation:
In the first operation, reversing the substring {S[3], .., S[6]} modifies the string to “10110010”.
In the second operation, reversing the substring {S[4], .. S[5]}modifies the string to “10101010”, which is alternating.

Input: S = “100001”
Output: -1
Explanation: Not possible to obtain an alternating binary string.

Approach: The idea is based on the observation that when a substring s[L, R] is reversed, then no more than two pairs s[L – 1], s[L] and s[R], S[R + 1] are changed. Moreover, one pair should be a consecutive pair of 00 and the other 11. So, the minimum number of operations can be obtained by pairing 00 with 11 or with the left/right border of S. Thus, the required number of operations is half of the number of consecutive pairs of the same character. Follow the steps below to solve the problem:

Traverse the string S to count the number of 1s and 0s and store them in sum1 and sum0 respectively.
If the absolute difference of sum1 and sum0 > 1, then print “-1”.
Otherwise, find the count of consecutive characters that are the same in the string S. Let that count be K for 1 and L for 0.
After completing the above steps, print the value of K as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum number
// of substrings required to be reversed
// to make the string S alternating
int minimumReverse(string s, int n)
{
    // Store count of consecutive pairs
    int k = 0 , l = 0 ;
 
    // Stores the count of 1s and 0s
    int sum1 = 0, sum0 = 0;
 
    // Traverse through the string
    for (int i = 1; i < n; i++) {
 
        if (s[i] == '1')
 
            // Increment 1s count
            sum1++;
        else
 
            // Increment 0s count
            sum0++;
 
        // Increment K if consecutive
        // same elements are found
        if (s[i] == s[i - 1]&& s[i] == '0')
            k++;
      else if( s[i] == s[i - 1]&& s[i] == '1')
        l++;
    }
   
    // Increment 1s count
    if(s[0]=='1')     
       sum1++;
    else  // Increment 0s count
       sum0++;
 
    // Check if it is possible or not
    if (abs(sum1 - sum0) > 1)
        return -1;
 
    // Otherwise, print the number
    // of required operations
    return max(k , l );
}
 
// Driver Code
int main()
{
    string S = "10001";
    int N = S.size();
 
    // Function Call
    cout << minimumReverse(S, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG 
{
 
  // Function to count the minimum number
  // of substrings required to be reversed
  // to make the string S alternating
  static int minimumReverse(String s, int n)
  {
 
    // Store count of consecutive pairs
    int k = 0 , l = 0 ;
 
    // Stores the count of 1s and 0s
    int sum1 = 0, sum0 = 0;
 
    // Traverse through the string
    for (int i = 1; i < n; i++) 
    {
 
      if (s.charAt(i) == '1')
 
        // Increment 1s count
        sum1++;
      else
 
        // Increment 0s count
        sum0++;
 
      // Increment K if consecutive
      // same elements are found
      if (s.charAt(i) == s.charAt(i - 1) && s.charAt(i) == '0')
        k++;
      else if( s.charAt(i) == s.charAt(i - 1) && s.charAt(i) == '1')
        l++;
    }
 
    // Increment 1s count
    if(s.charAt(0)=='1')     
      sum1++;
    else  // Increment 0s count
      sum0++;
 
    // Check if it is possible or not
    if (Math.abs(sum1 - sum0) > 1)
      return -1;
 
    // Otherwise, print the number
    // of required operations
    return Math.max(k , l);
  }
 
  // Driver code
  public static void main (String[] args) 
  {
    String S = "10001";
    int N = S.length();
 
    // Function Call
    System.out.print(minimumReverse(S, N));
 
  }
}
 
// This code is contributed by offbeat

Python3

# Python program for the above approach
 
# Function to count the minimum number
# of substrings required to be reversed
# to make the string S alternating
def minimumReverse(s, n):
   
    # Store count of consecutive pairs
    k = 0;
    l = 0;
 
    # Stores the count of 1s and 0s
    sum1 = 0;
    sum0 = 0;
 
    # Traverse through the string
    for i in range(1, n):
        if (s[i] == '1'):
 
            # Increment 1s count
            sum1 += 1;
        else:
 
            # Increment 0s count
            sum0 += 1;
 
        # Increment K if consecutive
        # same elements are found
        if (s[i] == s[i - 1] and s[i] == '0'):
            k += 1;
        elif (s[i] == s[i - 1] and s[i] == '1'):
            l += 1;
 
    # Increment 1s count
    if (s[0] == '1'):
        sum1 += 1;
    else:  # Increment 0s count
        sum0 += 1;
 
    # Check if it is possible or not
    if (abs(sum1 - sum0) > 1):
        return -1;
 
    # Otherwise, print the number
    # of required operations
    return max(k, l);
 
# Driver code
if __name__ == '__main__':
    S = "10001";
    N = len(S);
 
    # Function Call
    print(minimumReverse(S, N));
 
# This code is contributed by shikhasingrajput

C#

// C# program for the above approach
using System;
 
public class GFG 
{
 
  // Function to count the minimum number
  // of substrings required to be reversed
  // to make the string S alternating
  static int minimumReverse(String s, int n)
  {
 
    // Store count of consecutive pairs
    int k = 0 , l = 0 ;
 
    // Stores the count of 1s and 0s
    int sum1 = 0, sum0 = 0;
 
    // Traverse through the string
    for (int i = 1; i < n; i++) 
    {
 
      if (s[i] == '1')
 
        // Increment 1s count
        sum1++;
      else
 
        // Increment 0s count
        sum0++;
 
      // Increment K if consecutive
      // same elements are found
      if (s[i] == s[i-1] && s[i] == '0')
        k++;
      else if( s[i] == s[i-1] && s[i] == '1')
        l++;
    }
 
    // Increment 1s count
    if(s[0] == '1')     
      sum1++;
    else  // Increment 0s count
      sum0++;
 
    // Check if it is possible or not
    if (Math.Abs(sum1 - sum0) > 1)
      return -1;
 
    // Otherwise, print the number
    // of required operations
    return Math.Max(k , l);
  }
 
  // Driver code
  public static void Main(String[] args) 
  {
    String S = "10001";
    int N = S.Length;
 
    // Function Call
    Console.Write(minimumReverse(S, N));
  }
}
 
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
  // Function to count the minimum number
  // of substrings required to be reversed
  // to make the string S alternating
  function minimumReverse(s, n)
  {
  
    // Store count of consecutive pairs
    let k = 0 , l = 0 ;
  
    // Stores the count of 1s and 0s
    let sum1 = 0, sum0 = 0;
  
    // Traverse through the string
    for (let i = 1; i < n; i++)
    {
  
      if (s[i] == '1')
  
        // Increment 1s count
        sum1++;
      else
  
        // Increment 0s count
        sum0++;
  
      // Increment K if consecutive
      // same elements are found
      if (s[i] == s[i-1] && s[i] == '0')
        k++;
      else if( s[i] == s[i-1] && s[i] == '1')
        l++;
    }
  
    // Increment 1s count
    if(s[0] == '1')    
      sum1++;
    else  // Increment 0s count
      sum0++;
  
    // Check if it is possible or not
    if (Math.abs(sum1 - sum0) > 1)
      return -1;
  
    // Otherwise, print the number
    // of required operations
    return Math.max(k , l);
  }
      
// Driver code
         
    let S = "10001";
    let N = S.length;
  
    // Function Call
    document.write(minimumReverse(S, N));
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!