# 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 content of s doesn't matter, for each i in [0, n - k], we can // flip s[i..i + k] or not flip it. Therefore, there's 2^(n - k + 1) ways. return myPow(2, s.length() - k + 1); } private: constexpr static int kMod = 1'000'000'007; int myPow(long x, int n) { if (n == 0) return 1; if (n & 1) return x * myPow(x, n - 1) % kMod; return myPow(x * x % kMod, n / 2); } }; 
  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 content of s doesn't matter, for each i in [0, n - k], we can // flip s[i..i + k] or not flip it. Therefore, there's 2^(n - k + 1) ways. return (int) myPow(2, s.length() - k + 1); } private final static int kMod = 1_000_000_007; private long myPow(long x, int n) { if (n == 0) return 1; if (n % 2 == 1) return x * myPow(x, n - 1) % kMod; return myPow(x * x % kMod, n / 2); } } 
 1 2 3 4 5 class Solution: def countDistinctStrings(self, s: str, k: int) -> int: # Since content of s doesn't matter, for each i in [0, n - k], we can # flip s[i..i + k] or not flip it. Therefore, there's 2^(n - k + 1) ways. return pow(2, len(s) - k + 1, 1_000_000_007)