Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.
Пример:
Input: s = "abc"
Output: 7
👨💻 Алгоритм:
1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.
2⃣Инициализировать матрицу DP нулями.
Пройти по каждому символу строки:
Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ.
Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений.
3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7.
😎 Решение:
class Solution {
func countSubsequences(_ s: String) -> Int {
let MOD = 1000000007
var dp = [Int](repeating: 0, count: 26)
for c in s {
let index = Int(c.asciiValue! - Character("a").asciiValue!)
dp[index] = (dp.reduce(0, +) + 1) % MOD
}
return dp.reduce(0, +) % MOD
}
}Ставь 👍 и забирай 📚 Базу знаний