Сложность: 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 {
private static final int MOD = 1000000007;
public int countSubsequences(String s) {
int[] dp = new int[26];
for (char c : s.toCharArray()) {
int index = c - 'a';
dp[index] = (int)(((long)sum(dp) + 1) % MOD);
}
return sum(dp);
}
private int sum(int[] dp) {
int result = 0;
for (int val : dp) {
result = (result + val) % MOD;
}
return result;
}
}Ставь 👍 и забирай 📚 Базу знаний