Number of distinct binary strings after applying operations

Math String

63.9% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_distinct_strings(s: String, k: i32) -> i32 {
    let n = s.len() as i64;
    let k = k as i64;
    let modp = 1_000_000_007i64;
    let exp = n - k + 1;
    let mut result = 1i64;
    let mut base = 2i64;
    let mut e = exp;
    while e > 0 {
      if e & 1 == 1 { result = result * base % modp; }
      base = base * base % modp;
      e >>= 1;
    }
    result as i32
  }
}