Number of Distinct Binary Strings After Applying Operations

Number of Distinct Binary Strings After Applying Operations - Problem

Math String Medium

You are given a binary string s and a positive integer k. You can apply the following operation on the string any number of times:

Choose any substring of size k from s and flip all its characters, that is, turn all 1's into 0's, and all 0's into 1's.

Return the number of distinct strings you can obtain. Since the answer may be too large, return it modulo 10⁹ + 7.

Note that:

A binary string is a string that consists only of the characters 0 and 1.
A substring is a contiguous part of a string.

Input & Output

Example 1 — Basic Case

$ Input: s = "001", k = 2

› Output: 4

💡 Note: We can flip positions [0,1] to get "111", or flip [1,2] to get "010". From these we can generate "000", "100", and "101". Total distinct strings: {"001", "111", "010", "000", "100", "101"} but "100" appears twice, so we have 4 unique strings.

Example 2 — Single Operation

$ Input: s = "10", k = 2

› Output: 2

💡 Note: We can apply the flip operation at position 0 to get "01". So we have 2 distinct strings: "10" and "01".

Example 3 — No Operations Possible

$ Input: s = "1", k = 2

› Output: 1

💡 Note: String length is 1 but k=2, so no flip operations are possible. Only the original string "1" exists.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only '0' and '1'
1 ≤ k ≤ s.length

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string s="001" and flip length k=2

Operations

Apply k-flips at different positions to generate new strings

Output

Count total distinct reachable strings

Key Takeaway

🎯 Key Insight: Flip operations form a mathematical group - use linear algebra to count reachable states efficiently

Asked in

G Google 15 M Microsoft 12

The key insight is modeling flip operations as linear transformations over GF(2). Each k-flip creates a row in a matrix, and the rank determines how many distinct states are reachable. Best approach uses Linear Algebra with Gaussian elimination. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Algebra over GF(2)	O(n³)	O(n²)	Model operations as linear transformations in binary field
Brute Force with BFS	O(2^n)	O(2^n)	Generate all possible strings by trying every operation sequence

Linear Algebra over GF(2) — Algorithm Steps

Step 1: Create operation matrix where each row represents a k-flip
Step 2: Compute rank of the matrix using Gaussian elimination in GF(2)
Step 3: Answer is 2^rank since we can reach 2^rank distinct states

Visualization

Tap to expand

Step-by-Step Walkthrough

Operation Matrix

Each row represents one k-flip operation

Row Reduction

Gaussian elimination in GF(2)

Count Rank

Number of linearly independent operations

Compute Answer

2^rank gives total reachable states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

long long power(long long base, int exp, int mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp / 2;
        base = (base * base) % mod;
    }
    return result;
}

int solution(char* s, int k) {
    int n = strlen(s);
    
    // Create operation matrix
    int matrix[20][20];
    memset(matrix, 0, sizeof(matrix));
    
    for (int i = 0; i <= n - k; i++) {
        for (int j = i; j < i + k; j++) {
            matrix[i][j] = 1;
        }
    }
    
    // Gaussian elimination
    int rank = 0;
    int rows = n - k + 1;
    
    for (int col = 0; col < n; col++) {
        // Find pivot
        int pivotRow = -1;
        for (int row = rank; row < rows; row++) {
            if (matrix[row][col] == 1) {
                pivotRow = row;
                break;
            }
        }
        
        if (pivotRow == -1) continue;
        
        // Swap rows
        if (pivotRow != rank) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[rank][j];
                matrix[rank][j] = matrix[pivotRow][j];
                matrix[pivotRow][j] = temp;
            }
        }
        
        // Eliminate
        for (int row = 0; row < rows; row++) {
            if (row != rank && matrix[row][col] == 1) {
                for (int j = 0; j < n; j++) {
                    matrix[row][j] ^= matrix[rank][j];
                }
            }
        }
        
        rank++;
    }
    
    return power(2, rank, MOD);
}

int main() {
    char s[21];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Gaussian elimination on n×n matrix takes O(n³) operations

⚠ Quadratic Growth

Space Complexity

O(n²)

Matrix of size (n-k+1) × n to represent all operations

⚠ Quadratic Space

15.2K Views

Medium Frequency

~35 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Algebra over GF(2) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler