2327. Number of People Aware of a Secret

T: O(n)

S: O(n)

class Solution {
    //      0  1  2  3. 4. 5  6
    // dp: [0, 1, 0, 1, 1, 1, 0]
    //               1  2. 3. 4      i - delay
    //                     1  2
    private static int MOD = 1_000_000_007;
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long[] dp = new long[n+1]; // 1~n
        dp[1] = 1;
        long shareCount = 0;
        for (int i = 2; i <= n; i++) {
            if (i - delay > 0) { // index start from 1
                shareCount = (shareCount + dp[i - delay]) % MOD; // start to share (will delay days to share)
            }// i = 3 , shareCount = 1 -> because delay, so i = 3 (day=3 , will share day=1's count)
            // i = 4, shareCount = 1
            // i = 5, shareCount = 2 
            // i = 6, -> because delay, so i = 6 (day=6 , will share day=4's count), shareCount = 1 + 1 = 2 (B not forget so B share, and C is delay share from day4, so add 2)

            if (i - forget > 0) { // index start from 1
                shareCount = (shareCount - dp[i - forget] + MOD) % MOD; // forget also like delay (delay forget)
            } // i = 5, shareCount = 2 - 1 = 1, so i = 5(day = 5) , will forget day 1's count
            // i = 6, no one forget dp[6 - 4] = dp[2] = 0

            dp[i] = shareCount; // dp[3] = 1, dp[4] = 1, dp[5] = 1, dp[6] = 2
        }

        // result is the total of shareCount from each active day(not forget, so we cal from not forget day)
        long result = 0;
        for (int i = n - forget + 1; i <= n; i++) { // 3 to 6
            result = (result + dp[i]) % MOD; // 1 +1 + 1+2 = 5
        }

        return (int)(result);
    }
}

/**
https://www.youtube.com/watch?v=6AGTzDmReOw


dp[i]:  the number of people found the secret in ith day
running shareCount to store the shareCount in window

T: O(n)
S: O(n)


minus a big number, safer way is to add MOD again then % MOD,
or it will become negative number
shareCount = (shareCount - dp[i - forget] + MOD) % MOD;
 */