Count Number of Distinct Binary Strings After Applying Flip Operations

Convert a Binary String to another by flipping prefixes minimum number of times

Minimize Operation to Make Array Non-decreasing or Non-increasing

Given a binary string s and a positive integer k. In a operation you can repeatedly choose any substring of length k in s and flip all its characters (0s to 1s, 1s to 0s). The task is to return the number of distinct strings that can be obtained, modulo 10^9 + 7. You can perform the flip operation any number of times.

Example:

Input: s = “1001”, k = 3
Output: 4
Explanation: The four distinct substrings that can be obtained are:

“1001” (no operation applied)
“0111” (applying one operation to the substring starting at index 0)
“1110” (applying one operation to the substring starting at index 1)
“0000” (applying one operation to both the substrings starting at indices 0 and 1)
Input: s = “10110”, k = 5
Output: 2
Explanation: The two distinct substrings that can be obtained are:

“10110” (no operation applied)
“01001” (applying one operation to the whole string)

Approach:

The left n-k+1 bits can change to any combination, but the right k-1 bits have a fixed relationship with the kth bit from the right. Therefore the answer to the problem is pow(2, n-k+1).

Below are detailed approach:

We use the following to denote the string, where the 1st from the right is denoted as 1, 2nd as 2, so on and so forth.

n, n-1, …. k+1, k, k-1, k-2, …., 3, 2, 1

We can easily set the bit n to k with any possible ways, therefore we have 2^(n-k+1) ways.

But, from the k-1 bit on, whatever the original k-1 bit is 0 or 1, the k-1 bit will tightly couple up with the k bit (as both of them participate in the [2k-2, … k, k-1] group change. If the k bit flip, k-1 bit will flip along. They either change together or do-not-change together.

Likewise, when k-2 bit participates in the change of the [2k-3, … k, k-1, k-2] group, the k-2 bit tightly couples up with the k and k-1 bits. These three bits either change together or do-not-change together.

This relationship goes on to the end of the string.

Steps-by-step approach:

Get the length of the input string s as n.
The number of distinct substrings is 2^(n-k+1), as each character can be either included or excluded, and the number of distinct characters in the substring must be at least k.
Return the result of pow(2, n-k+1) to get the final count of distinct substrings.

Below are the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;

const long MOD = (long)1e9 + 7;

// Function to count the number of distinct substrings in
// the given string 's' where the number of distinct
// characters in each substring is at least 'k'
int countDistinctStrings(string s, int k)
{
    const int n = s.size();

    // The number of distinct substrings is 2^(n-k+1), since
    // each character can be either included or excluded in
    // the substring, and the number of distinct characters
    // in the substring must be at least 'k'
    return pow(2, n - k + 1);
}

// Driver code
int main()
{
    string s = "1001";
    int k = 3;

    int result = countDistinctStrings(s, k);
    cout << "Number of distinct substrings: " << result
         << endl;
    return 0;
}

Java

public class Main {

    // Function to count the number of distinct substrings
    // in the given string 's' where the number of distinct
    // characters in each substring is at least 'k'
    public static int countDistinctStrings(String s, int k)
    {
        // The length of the string
        int n = s.length();

        // The number of distinct substrings is 2^(n-k+1),
        // since each character can be either included or
        // excluded in the substring, and the number of
        // distinct characters in the substring must be at
        // least 'k'
        return (int)Math.pow(2, n - k + 1);
    }

    // Driver code
    public static void main(String[] args)
    {
        String s = "1001";
        int k = 3;

        int result = countDistinctStrings(s, k);
        System.out.println("Number of distinct substrings: "
                           + result);
    }
}

Python

# Importing the math module for the pow function
import math

# Function to count the number of distinct substrings in
# the given string 's' where the number of distinct
# characters in each substring is at least 'k'


def countDistinctStrings(s, k):
    # The length of the string
    n = len(s)

    # The number of distinct substrings is 2^(n-k+1), since
    # each character can be either included or excluded in
    # the substring, and the number of distinct characters
    # in the substring must be at least 'k'
    return int(math.pow(2, n - k + 1))


# Driver code
if __name__ == "__main__":
    s = "1001"
    k = 3

    result = countDistinctStrings(s, k)
    print("Number of distinct substrings: ", result)

JavaScript

const MOD = 1e9 + 7;

// Function to count the number of distinct substrings in
// the given string 's' where the number of distinct
// characters in each substring is at least 'k'
function countDistinctStrings(s, k) {
    const n = s.length;

    // The number of distinct substrings is 2^(n-k+1), since
    // each character can be either included or excluded in
    // the substring, and the number of distinct characters
    // in the substring must be at least 'k'
    return Math.pow(2, n - k + 1);
}

// Driver code
const s = "1001";
const k = 3;

const result = countDistinctStrings(s, k);
console.log(`Number of distinct substrings: ${result}`);
// This code is contributed by Ayush Mishra

Output

Number of distinct substrings: 4

Time Complexity: O(log n), where n is the length of the input string s
Auxiliary Space: O(1)

Tags:

#combinatorics #Microsoft #DSA #Strings #Microsoft #Strings

Convert a Binary String to another by flipping prefixes minimum number of times

Minimize Operation to Make Array Non-decreasing or Non-increasing

Count Number of Distinct Binary Strings After Applying Flip Operations

Contact Us