Generate Binary String with equal number of 01 and 10 Subsequence

0 0 6 minutes read

Given an integer N (N > 2), the task is to generate a binary string of size N that consists of equal numbers of “10” & “01” subsequences and also the string should contain at least one ‘0’ and one ‘1’

Note: If multiple such strings exist, print any.

Examples:

Input: 4
Output: 0110
Explanation : Here, 0110 string consists equal count of ’01’ and ’10’
subsequence and it consists at least one occurrence of 0 as well as 1.

Input: 3
Output: 010
Explanation : Here, 010 string consists equal count of ’01’ and ’10’
subsequence and it consists at least one occurrence of 0 as well as 1.

Naive approach:

The idea is to generate every possible binary string(string which consists of only 0’s and 1’s) and find a substring with equal number of ’01’ and ’10’ subsequence.

Time Complexity: O(2^N * 2^N) = O(4^N) because each string also has 2^N subsequences.
Auxiliary Space: O(N)

Efficient approach: To solve the problem follow the below observations:

Case 1 (If N is even): Then add 1s at N/2 and (N/2 – 1) index, and add 0s to the rest of the string. So the count of ’10’ and ’01’ will be same which is equal to 2*(N/2 – 1) = (N – 2) and string also consists of at least once occurrence of 0 and 1.

For example:

If N = 4, that means N is even, then add 1 at index N/2 =2 and (N/2)-1 = 1 .

And add 0s at remaining positions from 0 to 3 .

Hence, string is “0110”.

Case 2 (If N is odd): Then add 1s at middle and add 0s to the rest of the string. So the count of ’10’ and ’01’ is same which is equal to N/2 and string also consists at least once occurrence of 0 and 1.

For example:

If N=3, that means N is odd then add 1 at index N/2=1.

And add 0s at remaining positions from 0 to 2.

Hence, string is “010”.

Follow the below steps to implement the above approach:

Take an empty string s.
Now check if N is even or odd:
- If N is even, iterate from 0 to N – 1 and add ‘1’ only at the N/2 and (N/2 – 1) index and ‘0’ on the other indices of the string.
- If N is odd, iterate from 0 to N-1 and add ‘1’ only at the N/2 index and ‘0’ in all other indices of the string.
Now, return the constructed string.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
string makeString(int n)
{
    string s = "";
 
    // If n is even then follow this block
    int mid = n / 2;
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
 
            // If i is at middle of n and
            // previous middle of n
            // then add 1 into the string
            if (i == mid || i == mid - 1) {
                s += "1";
            }
 
            // Otherwise, add 0 to the string
            else {
                s += "0";
            }
        }
    }
 
    // If n is odd then follow this block
    else {
        for (int i = 0; i < n; i++) {
 
            // If i is equal to mid then
            // add 1 to the string
            if (i == mid) {
                s += "1";
            }
 
            // Otherwise add 0 to the string
            else {
                s += "0";
            }
        }
 
        // Return the constructed string
        return s;
    }
}
 
// Driver code
int main()
{
    int N = 4;
 
    // Function call
    cout << makeString(N);
    return 0;
}

Java

// Java code to implement the approach
 
 
import java.util.*;
 
class GFG{
 
static String makeString(int n)
{
    String s = "";
 
    // If n is even then follow this block
    int mid = n / 2;
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
 
            // If i is at middle of n and
            // previous middle of n
            // then add 1 into the String
            if (i == mid || i == mid - 1) {
                s += "1";
            }
 
            // Otherwise, add 0 to the String
            else {
                s += "0";
            }
        }
    }
 
    // If n is odd then follow this block
    else {
        for (int i = 0; i < n; i++) {
 
            // If i is equal to mid then
            // add 1 to the String
            if (i == mid) {
                s += "1";
            }
 
            // Otherwise add 0 to the String
            else {
                s += "0";
            }
        }
 
        // Return the constructed String
        return s;
    }
    return s;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4;
 
    // Function call
    System.out.print(makeString(N));
}
}
 
// This code contributed by shikhasingrajput

Python3

# Python code to implement the approach
def makeString(n):
    s = ""
     
    # If n is even then follow this block
    mid = n/2
    if(n % 2 == 0):
        for i in range(n):
            # If i is at middle of n and previous 
            # middle of n then add 1 into the string
            if(i == mid or i == mid-1):
                s += "1"
            # Otherwise, add 0 to the string.
            else:
                s += "0"
 
    # If n is odd then follow this block
    else:
        for i in range(n):
            # If i is equal to mid then add 1 to the string
            if i == mid:
                s += "1"
            # Otherwise add 0 to the string
            else:
                s += "0"
                # Return the constructed String
        return s
    return s
 
N = 4
 
# Function call
print(makeString(N))
 
# This code is contributed by lokeshmvs21.

C#

// C# code to implement the approach
 
using System;
 
public class GFG{
 
static String makeString(int n)
{
    string s = "";
 
    // If n is even then follow this block
    int mid = n / 2;
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
 
            // If i is at middle of n and
            // previous middle of n
            // then add 1 into the String
            if (i == mid || i == mid - 1) {
                s += "1";
            }
 
            // Otherwise, add 0 to the String
            else {
                s += "0";
            }
        }
    }
 
    // If n is odd then follow this block
    else {
        for (int i = 0; i < n; i++) {
 
            // If i is equal to mid then
            // add 1 to the String
            if (i == mid) {
                s += "1";
            }
 
            // Otherwise add 0 to the String
            else {
                s += "0";
            }
        }
 
        // Return the constructed String
        return s;
    }
    return s;
}
 
// Driver code
public static void Main(string[] args)
{
    int N = 4;
 
    // Function call
    Console.WriteLine(makeString(N));
}
}
 
// This code contributed by AnkThon

Javascript

<script>
// Javascript program for above approach
function makeString(n)
{
    let s = "";
 
    // If n is even then follow this block
    let mid = n / 2;
    if (n % 2 == 0) {
        for (let i = 0; i < n; i++) {
 
            // If i is at middle of n and
            // previous middle of n
            // then add 1 into the String
            if (i == mid || i == mid - 1) {
                s += "1";
            }
 
            // Otherwise, add 0 to the String
            else {
                s += "0";
            }
        }
    }
 
    // If n is odd then follow this block
    else {
        for (let i = 0; i < n; i++) {
 
            // If i is equal to mid then
            // add 1 to the String
            if (i == mid) {
                s += "1";
            }
 
            // Otherwise add 0 to the String
            else {
                s += "0";
            }
        }
 
        // Return the constructed String
        return s;
    }
    return s;
}
 
// Driver Code
    let N = 4;
 
    // Function call
    document.write(makeString(N));
      
     // This code is contributed by code_hunt.
</script>

Output

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

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!