Skip to main content
Talentd

Number of Distinct Binary Strings After Applying Operations - Solution & Explanation

MediumPremiumFree on FleetCodeMathString6 min readAsked at: Microsoft
Practice this problem

Problem Statement

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 109 + 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.

 

Example 1:

Input: s = "1001", k = 3
Output: 4
Explanation: We can obtain the following strings:
- Applying no operation on the string gives s = "1001".
- Applying one operation on the substring starting at index 0 gives s = "0111".
- Applying one operation on the substring starting at index 1 gives s = "1110".
- Applying one operation on both the substrings starting at indices 0 and 1 gives s = "0000".
It can be shown that we cannot obtain any other string, so the answer is 4.

Example 2:

Input: s = "10110", k = 5
Output: 2
Explanation: We can obtain the following strings:
- Applying no operation on the string gives s = "10110".
- Applying one operation on the whole string gives s = "01001".
It can be shown that we cannot obtain any other string, so the answer is 2.

 

Constraints:

  • 1 <= k <= s.length <= 105
  • s[i] is either 0 or 1.

Approach Overview

Problem Overview: You start with a binary string s of length n. In one operation, you can pick any index i and flip the k consecutive bits starting at i. The task is to compute how many distinct binary strings can be produced after applying any number of operations.

Approach 1: Brute Force with State Exploration (Exponential Time, Exponential Space)

One way to reason about the problem is to simulate every reachable string. Treat each binary string as a node in a graph and connect nodes if one operation transforms one string into another. Using BFS or DFS with a hash set avoids revisiting states. For every index i, flip the substring s[i..i+k-1] and push the result into the queue. This explores all reachable states but the total possibilities grow up to 2^n, giving O(2^n * n) time and O(2^n) space. This approach only works for very small strings and mainly helps build intuition about how operations combine.

Approach 2: Mathematical Observation (O(log n) time, O(1) space)

Each operation flips exactly k consecutive bits. There are n - k + 1 possible starting positions for this operation. Think of every operation as a binary choice: apply it or not. Because flipping twice cancels out, applying the same operation multiple times has no additional effect. The only thing that matters is whether each of the n - k + 1 operations is applied an odd or even number of times.

These operations act like independent binary toggles that combine using XOR behavior. Any sequence of operations can be represented as a combination of those n - k + 1 choices. Each choice doubles the number of reachable strings. Therefore the total number of distinct strings is 2^(n - k + 1).

The initial string does not affect the count. Operations simply toggle bits relative to the starting configuration. The only work left is computing the value modulo 1e9 + 7 using fast modular exponentiation. That gives O(log n) time and O(1) extra space.

This reasoning relies on properties of bit flipping and XOR-style transformations commonly used in math and string manipulation problems.

Recommended for interviews: The mathematical observation is the expected solution. A brute force explanation shows you understand the transformation space, but recognizing that each valid operation position contributes an independent binary choice demonstrates stronger algorithmic insight.

Solution

Assume the length of the string s is n. Then there are n - k + 1 substrings of length k, and each substring can be flipped, so there are 2^{n - k + 1} ways to flip.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string s.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force State Exploration (BFS/DFS)O(2^n * n)O(2^n)Useful only for very small n or for understanding how operations generate new states
Mathematical Counting + Modular ExponentiationO(log n)O(1)Optimal solution for all constraints; relies on observing n-k+1 independent flip operations

Video Solution

LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,249 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Distinct Binary Strings After Applying Operations easy or hard?
The problem is rated Medium because the key challenge is recognizing the mathematical pattern. Once you realize that each operation position contributes an independent binary choice, the implementation becomes trivial.
Number of Distinct Binary Strings After Applying Operations Python/Java solution
The implementation is very short. Compute n = len(s), calculate exponent = n - k + 1, and return pow(2, exponent, 1_000_000_007) in Python or use fast modular exponentiation in Java. This directly gives the number of distinct reachable strings.
How to solve Number of Distinct Binary Strings After Applying Operations in O(n)?
A full simulation would require exploring up to 2^n states, which is inefficient. Instead, observe that there are n-k+1 independent operations and each can be applied or skipped. This reduces the problem to computing 2^(n-k+1), which can be calculated using fast exponentiation in O(log n) time.
What is the best approach for Number of Distinct Binary Strings After Applying Operations?
The optimal approach uses a mathematical observation. There are exactly n - k + 1 possible positions where the k-length flip operation can start. Each position represents an independent binary decision (apply or not), so the number of reachable strings is 2^(n-k+1). The result is computed using modular exponentiation in O(log n) time and O(1) space.
Is Number of Distinct Binary Strings After Applying Operations asked at Google/Amazon/Meta?
Problems involving bit manipulation, combinatorics, and operation independence frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require recognizing XOR-style transformations or counting reachable states are common in mid-level interview rounds.
What data structure is used in Number of Distinct Binary Strings After Applying Operations?
The optimal solution does not require complex data structures. It relies on mathematical reasoning and modular exponentiation. Brute force approaches may use a hash set and queue for BFS to track visited strings.
What is the time complexity of Number of Distinct Binary Strings After Applying Operations?
The optimal solution runs in O(log n) time due to fast modular exponentiation used to compute 2^(n-k+1) mod 1e9+7. Space complexity is O(1) since only a few integer variables are required.

Ready to solve this problem?

Practice Number of Distinct Binary Strings After Applying Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of K Consecutive Bit Flips