package daily.hard

fun main() {
    // 940. 不同的子序列 II
    // https://leetcode.cn/problems/distinct-subsequences-ii/
    println(distinctSubseqII("blljuffdyfrkqtwfyfztpdiyktrhftgtabxxoibcclbjvirnqyynkyaqlxgyybkgyzvcahmytjdqqtctirnxfjpktxmjkojlvvrr"))
}

fun distinctSubseqII(s: String): Int {
    val mod = (Math.pow(10.0, 9.0) + 7).toInt()
    val dp = IntArray(s.length)
    val repeatArray = IntArray(26)
    dp[0] = 1 // 以 s[0] 结尾的字符串的子序列数量，只有1个
    repeatArray[s[0] - 'a'] = 1 // s[0] 对应的字符的重复次数，是1
    for (i in 1 until s.length) {
        val newCount = ((dp[i-1] + 1).rem(mod) + mod - repeatArray[s[i] - 'a']).rem(mod)
        dp[i] = (dp[i-1] + newCount).rem(mod)
        repeatArray[s[i] - 'a'] += newCount
    }
    return dp[s.length - 1]
}

/**
 * 不考虑大数的版本，没有取余操作
 * 参考题解
 * https://leetcode.cn/problems/distinct-subsequences-ii/solution/zhua-wa-mou-si-tu-jie-leetcode-by-muse-7-j2sy/
 */
fun distinctSubseqII1(s: String): Int {
    val dp = IntArray(s.length)
    val repeatArray = IntArray(26)
    dp[0] = 1 // 以 s[0] 结尾的字符串的子序列数量，只有1个
    repeatArray[s[0] - 'a'] = 1 // s[0] 对应的字符的重复次数，是1
    for (i in 1 until s.length) {
        val newCount = dp[i-1] + 1 - repeatArray[s[i] - 'a']
        dp[i] = dp[i-1] + newCount
        // 注意这里是 +=，不能直接赋值 repeatArray[s[i] - 'a'] = newCount，因为这里 newCount 是减去了上一次重复的次数的- repeatArray[s[i] - 'a']
        repeatArray[s[i] - 'a'] += newCount
    }
    return dp[s.length - 1]
}