Сложность: 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.
😎 Решение:
function countSubsequences($s) {
$MOD = 1000000007;
$dp = array_fill(0, 26, 0);
foreach (str_split($s) as $c) {
$index = ord($c) - ord('a');
$dp[$index] = (array_sum($dp) + 1) % $MOD;
}
return array_sum($dp) % $MOD;
}Ставь 👍 и забирай 📚 Базу знаний