# 2450. Number of Distinct Binary Strings After Applying Operations¶

• Time: $O(\log n)$
• Space: $O(\log n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: int countDistinctStrings(string s, int k) { // Since the content of s doesn't matter, for each i in [0, n - k], we can // flip s[i..i + k] or don't flip it. Therefore, there's 2^(n - k + 1) ways. return modPow(2, s.length() - k + 1); } private: static constexpr int kMod = 1'000'000'007; long modPow(long x, long n) { if (n == 0) return 1; if (n % 2 == 1) return x * modPow(x % kMod, (n - 1)) % kMod; return modPow(x * x % kMod, (n / 2)) % kMod; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int countDistinctStrings(String s, int k) { // Since the content of s doesn't matter, for each i in [0, n - k], we can // flip s[i..i + k] or don't flip it. Therefore, there's 2^(n - k + 1) ways. return (int) modPow(2, s.length() - k + 1); } private static final int kMod = 1_000_000_007; private long modPow(long x, long n) { if (n == 0) return 1; if (n % 2 == 1) return x * modPow(x, n - 1) % kMod; return modPow(x * x % kMod, n / 2); } } 
 1 2 3 4 5 class Solution: def countDistinctStrings(self, s: str, k: int) -> int: # Since the content of s doesn't matter, for each i in [0, n - k], we can # flip s[i..i + k] or don't flip it. Therefore, there's 2^(n - k + 1) ways. return pow(2, len(s) - k + 1, 1_000_000_007)