Сложность: 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.
😎 Решение:
MOD = 10**9 + 7
def countSubsequences(s):
dp = [0] * 26
for c in s:
index = ord(c) - ord('a')
dp[index] = (sum(dp) + 1) % MOD
return sum(dp) % MOD
Ставь 👍 и забирай 📚 Базу знаний