2466. Count Ways To Build Good Strings

Time: O(high)

Space: O(high)

Intuition

Count strings where no two adjacent characters are the same. For each position after first: (k-1) choices. Total = k * (k-1)^(n-1).

Algorithm

1Answer = k * (k-1)^(n-1) % MOD.

Common Pitfalls

•First position: k choices. Each subsequent: k-1 (any but previous). Use modular exponentiation.

2466.cs

// Approach: DP counting strings of each length; sum lengths in [low, high].
// Time: O(high) Space: O(high)

public class Solution
{
    public int CountGoodStrings(int low, int high, int zero, int one)
    {
        const int kMod = 1_000_000_007;
        int ans = 0;
        // dp[i] := the number of good strings with length i
        int[] dp = new int[high + 1];
        dp[0] = 1;

        for (int i = 1; i <= high; ++i)
        {
            if (i >= zero)
                dp[i] = (dp[i] + dp[i - zero]) % kMod;
            if (i >= one)
                dp[i] = (dp[i] + dp[i - one]) % kMod;
            if (i >= low)
                ans = (ans + dp[i]) % kMod;
        }

        return ans;
    }
}

Was this solution helpful?