class066 一维动态规划
code1 509斐波那契数列
// 斐波那契数
// 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
// 也就是：F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1
// 给定 n ，请计算 F(n)
// 测试链接 : https://leetcode.cn/problems/fibonacci-number/
// 注意：最优解来自矩阵快速幂，时间复杂度可以做到O(log n)
// 后续课程一定会讲述！本节课不涉及！
dp[i]：从F(i)的值
=1,i=1
=i+dp[i-1],i>=2
f1 递归
f2 从顶到底 记忆化搜索
f3 从底到顶
f4 空间优化
package class066;
import java.util.Arrays;
// 斐波那契数
// 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
// 也就是：F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1
// 给定 n ，请计算 F(n)
// 测试链接 : https://leetcode.cn/problems/fibonacci-number/
// 注意：最优解来自矩阵快速幂，时间复杂度可以做到O(log n)
// 后续课程一定会讲述！本节课不涉及！
public class Code01_FibonacciNumber {
public static int fib1(int n) {
return f1(n);
}
public static int f1(int i) {
if (i == 0) {
return 0;
}
if (i == 1) {
return 1;
}
return f1(i - 1) + f1(i - 2);
}
public static int fib2(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, -1);
return f2(n, dp);
}
public static int f2(int i, int[] dp) {
if (i == 0) {
return 0;
}
if (i == 1) {
return 1;
}
if (dp[i] != -1) {
return dp[i];
}
int ans = f2(i - 1, dp) + f2(i - 2, dp);
dp[i] = ans;
return ans;
}
public static int fib3(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static int fib4(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int lastLast = 0, last = 1;
for (int i = 2, cur; i <= n; i++) {
cur = lastLast + last;
lastLast = last;
last = cur;
}
return last;
}
}code2 983最低票价
// 最低票价
// 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
// 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
// 每一项是一个从 1 到 365 的整数
// 火车票有 三种不同的销售方式
// 一张 为期1天 的通行证售价为 costs[0] 美元
// 一张 为期7天 的通行证售价为 costs[1] 美元
// 一张 为期30天 的通行证售价为 costs[2] 美元
// 通行证允许数天无限制的旅行
// 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
// 那么我们可以连着旅行 7 天(第2~8天)
// 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
// 测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/
dp[i]:以i…天的最低票价
=math.min(cost[k]+dp[j]),(k:3种方案，j:方案到期天数)
f1 递归 有重复调用
[3,4,9,20,50,...]
0 1 2 3 4
1天 1天 1天 1天 f(4,)
7天 1天 f(4,)
30天 f(4,)f2 记忆化搜索 带缓存的搜索
f3 动态规划
package class066;
import java.util.Arrays;
// 最低票价
// 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
// 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
// 每一项是一个从 1 到 365 的整数
// 火车票有 三种不同的销售方式
// 一张 为期1天 的通行证售价为 costs[0] 美元
// 一张 为期7天 的通行证售价为 costs[1] 美元
// 一张 为期30天 的通行证售价为 costs[2] 美元
// 通行证允许数天无限制的旅行
// 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
// 那么我们可以连着旅行 7 天(第2~8天)
// 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
// 测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/
public class Code02_MinimumCostForTickets {
// 无论提交什么方法都带着这个数组 0 1 2
public static int[] durations = { 1, 7, 30 };
// 暴力尝试
public static int mincostTickets1(int[] days, int[] costs) {
return f1(days, costs, 0);
}
// days[i..... 最少花费是多少
public static int f1(int[] days, int[] costs, int i) {
if (i == days.length) {
// 后续已经无旅行了
return 0;
}
// i下标 : 第days[i]天，有一场旅行
// i.... 最少花费是多少
int ans = Integer.MAX_VALUE;
for (int k = 0, j = i; k < 3; k++) {
// k是方案编号 : 0 1 2
while (j < days.length && days[i] + durations[k] > days[j]) {
// 因为方案2持续的天数最多，30天
// 所以while循环最多执行30次
// 枚举行为可以认为是O(1)
j++;
}
ans = Math.min(ans, costs[k] + f1(days, costs, j));
}
return ans;
}
// 暴力尝试改记忆化搜索
// 从顶到底的动态规划
public static int mincostTickets2(int[] days, int[] costs) {
int[] dp = new int[days.length];
for (int i = 0; i < days.length; i++) {
dp[i] = Integer.MAX_VALUE;
}
return f2(days, costs, 0, dp);
}
public static int f2(int[] days, int[] costs, int i, int[] dp) {
if (i == days.length) {
return 0;
}
if (dp[i] != Integer.MAX_VALUE) {
return dp[i];
}
int ans = Integer.MAX_VALUE;
for (int k = 0, j = i; k < 3; k++) {
while (j < days.length && days[i] + durations[k] > days[j]) {
j++;
}
ans = Math.min(ans, costs[k] + f2(days, costs, j, dp));
}
dp[i] = ans;
return ans;
}
// 严格位置依赖的动态规划
// 从底到顶的动态规划
public static int MAXN = 366;
public static int[] dp = new int[MAXN];
public static int mincostTickets3(int[] days, int[] costs) {
int n = days.length;
Arrays.fill(dp, 0, n + 1, Integer.MAX_VALUE);
dp[n] = 0;
for (int i = n - 1; i >= 0; i--) {
for (int k = 0, j = i; k < 3; k++) {
while (j < days.length && days[i] + durations[k] > days[j]) {
j++;
}
dp[i] = Math.min(dp[i], costs[k] + dp[j]);
}
}
return dp[0];
}
}code3 91解码方法
// 解码方法
// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// ‘A’ -> “1”
// ‘B’ -> “2”
// …
// ‘Z’ -> “26”
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
// 例如，“11106” 可以映射为：“AAJF”、“KJF”
// 注意，消息不能分组为(1 11 06)，因为 “06” 不能映射为 “F”
// 这是由于 “6” 和 “06” 在映射中并不等价
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
// 题目数据保证答案肯定是一个 32位 的整数
// 测试链接 : https://leetcode.cn/problems/decode-ways/
dp[i]：以i开始的[i…]的解码方法个数
=0,s[i]==‘0’
=dp[i+1]+1
+=dp[i+2],s[i] s[i+1]构成合法解码
f1 递归
f2 记忆化搜索
f3 动态规划
package class066;
import java.util.Arrays;
// 解码方法
// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
// 例如，"11106" 可以映射为："AAJF"、"KJF"
// 注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F"
// 这是由于 "6" 和 "06" 在映射中并不等价
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
// 题目数据保证答案肯定是一个 32位 的整数
// 测试链接 : https://leetcode.cn/problems/decode-ways/
public class Code03_DecodeWays {
// 暴力尝试
public static int numDecodings1(String s) {
return f1(s.toCharArray(), 0);
}
// s : 数字字符串
// s[i....]有多少种有效的转化方案
public static int f1(char[] s, int i) {
if (i == s.length) {
return 1;
}
int ans;
if (s[i] == '0') {
ans = 0;
} else {
ans = f1(s, i + 1);
if (i + 1 < s.length && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26) {
ans += f1(s, i + 2);
}
}
return ans;
}
// 暴力尝试改记忆化搜索
public static int numDecodings2(String s) {
int[] dp = new int[s.length()];
Arrays.fill(dp, -1);
return f2(s.toCharArray(), 0, dp);
}
public static int f2(char[] s, int i, int[] dp) {
if (i == s.length) {
return 1;
}
if (dp[i] != -1) {
return dp[i];
}
int ans;
if (s[i] == '0') {
ans = 0;
} else {
ans = f2(s, i + 1, dp);
if (i + 1 < s.length && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26) {
ans += f2(s, i + 2, dp);
}
}
dp[i] = ans;
return ans;
}
// 严格位置依赖的动态规划
public static int numDecodings3(String str) {
char[] s = str.toCharArray();
int n = s.length;
int[] dp = new int[n + 1];
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '0') {
dp[i] = 0;
} else {
dp[i] = dp[i + 1];
if (i + 1 < s.length && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26) {
dp[i] += dp[i + 2];
}
}
}
return dp[0];
}
// 严格位置依赖的动态规划 + 空间压缩
public static int numDecodings4(String s) {
// dp[i+1]
int next = 1;
// dp[i+2]
int nextNext = 0;
for (int i = s.length() - 1, cur; i >= 0; i--) {
if (s.charAt(i) == '0') {
cur = 0;
} else {
cur = next;
if (i + 1 < s.length() && ((s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0') <= 26) {
cur += nextNext;
}
}
nextNext = next;
next = cur;
}
return next;
}
}code4 639解码方法 II
// 解码方法 II
// 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
// ‘A’ -> “1”
// ‘B’ -> “2”
// …
// ‘Z’ -> “26”
// 要 解码 一条已编码的消息，所有的数字都必须分组
// 然后按原来的编码方案反向映射回字母（可能存在多种方式）
// 例如，“11106” 可以映射为：“AAJF”、“KJF”
// 注意，像 (1 11 06) 这样的分组是无效的，“06"不可以映射为’F’
// 除了上面描述的数字字母映射方案，编码消息中可能包含 '’ 字符
// 可以表示从 ‘1’ 到 ‘9’ 的任一数字（不包括 ‘0’）
// 例如，"1” 可以表示 “11”、“12”、“13”、“14”、“15”、“16”、“17”、“18” 或 “19”
// 对 “1*” 进行解码，相当于解码该字符串可以表示的任何编码消息
// 给你一个字符串 s ，由数字和 ‘*’ 字符组成，返回 解码 该字符串的方法 数目
// 由于答案数目可能非常大，返回10^9 + 7的模
// 测试链接 : https://leetcode.cn/problems/decode-ways-ii/
dp[i]：以i开始的[i…]的解码方法个数
=0,s[i]= =‘0’
=dp[i+1]x9,s[i]==‘*’
+=dp[i+2],s[i] s[i+1]构成合法解码
f1 递归
f2 记忆化搜索
package class066;
import java.util.Arrays;
// 解码方法 II
// 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 一条已编码的消息，所有的数字都必须分组
// 然后按原来的编码方案反向映射回字母（可能存在多种方式）
// 例如，"11106" 可以映射为："AAJF"、"KJF"
// 注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F'
// 除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符
// 可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）
// 例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"
// 对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
// 给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目
// 由于答案数目可能非常大，返回10^9 + 7的模
// 测试链接 : https://leetcode.cn/problems/decode-ways-ii/
public class Code04_DecodeWaysII {
// 没有取模逻辑
// 最自然的暴力尝试
public static int numDecodings1(String str) {
return f1(str.toCharArray(), 0);
}
// s[i....] 有多少种有效转化
public static int f1(char[] s, int i) {
if (i == s.length) {
return 1;
}
if (s[i] == '0') {
return 0;
}
// s[i] != '0'
// 2) i想单独转
int ans = f1(s, i + 1) * (s[i] == '*' ? 9 : 1);
// 3) i i+1 一起转化 <= 26
if (i + 1 < s.length) {
// 有i+1位置
if (s[i] != '*') {
if (s[i + 1] != '*') {
// num num
// i i+1
if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
ans += f1(s, i + 2);
}
} else {
// num *
// i i+1
if (s[i] == '1') {
ans += f1(s, i + 2) * 9;
}
if (s[i] == '2') {
ans += f1(s, i + 2) * 6;
}
}
} else {
if (s[i + 1] != '*') {
// * num
// i i+1
if (s[i + 1] <= '6') {
ans += f1(s, i + 2) * 2;
} else {
ans += f1(s, i + 2);
}
} else {
// * *
// i i+1
// 11 12 ... 19 21 22 ... 26 -> 一共15种可能
// 没有10、20，因为*只能变1~9，并不包括0
ans += f1(s, i + 2) * 15;
}
}
}
return ans;
}
public static long mod = 1000000007;
public static int numDecodings2(String str) {
char[] s = str.toCharArray();
long[] dp = new long[s.length];
Arrays.fill(dp, -1);
return (int) f2(s, 0, dp);
}
public static long f2(char[] s, int i, long[] dp) {
if (i == s.length) {
return 1;
}
if (s[i] == '0') {
return 0;
}
if (dp[i] != -1) {
return dp[i];
}
long ans = f2(s, i + 1, dp) * (s[i] == '*' ? 9 : 1);
if (i + 1 < s.length) {
if (s[i] != '*') {
if (s[i + 1] != '*') {
if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
ans += f2(s, i + 2, dp);
}
} else {
if (s[i] == '1') {
ans += f2(s, i + 2, dp) * 9;
}
if (s[i] == '2') {
ans += f2(s, i + 2, dp) * 6;
}
}
} else {
if (s[i + 1] != '*') {
if (s[i + 1] <= '6') {
ans += f2(s, i + 2, dp) * 2;
} else {
ans += f2(s, i + 2, dp);
}
} else {
ans += f2(s, i + 2, dp) * 15;
}
}
}
ans %= mod;
dp[i] = ans;
return ans;
}
public static int numDecodings3(String str) {
char[] s = str.toCharArray();
int n = s.length;
long[] dp = new long[n + 1];
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
if (s[i] != '0') {
dp[i] = (s[i] == '*' ? 9 : 1) * dp[i + 1];
if (i + 1 < n) {
if (s[i] != '*') {
if (s[i + 1] != '*') {
if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
dp[i] += dp[i + 2];
}
} else {
if (s[i] == '1') {
dp[i] += dp[i + 2] * 9;
}
if (s[i] == '2') {
dp[i] += dp[i + 2] * 6;
}
}
} else {
if (s[i + 1] != '*') {
if (s[i + 1] <= '6') {
dp[i] += dp[i + 2] * 2;
} else {
dp[i] += dp[i + 2];
}
} else {
dp[i] += dp[i + 2] * 15;
}
}
}
dp[i] %= mod;
}
}
return (int) dp[0];
}
public static int numDecodings4(String str) {
char[] s = str.toCharArray();
int n = s.length;
long cur = 0, next = 1, nextNext = 0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] != '0') {
cur = (s[i] == '*' ? 9 : 1) * next;
if (i + 1 < n) {
if (s[i] != '*') {
if (s[i + 1] != '*') {
if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
cur += nextNext;
}
} else {
if (s[i] == '1') {
cur += nextNext * 9;
}
if (s[i] == '2') {
cur += nextNext * 6;
}
}
} else {
if (s[i + 1] != '*') {
if (s[i + 1] <= '6') {
cur += nextNext * 2;
} else {
cur += nextNext;
}
} else {
cur += nextNext * 15;
}
}
}
cur %= mod;
}
nextNext = next;
next = cur;
cur = 0;
}
return (int) next;
}
}code5 264. 丑数 II
// 丑数 II
// 给你一个整数 n ，请你找出并返回第 n 个 丑数
// 丑数 就是只包含质因数 2、3 或 5 的正整数
// 测试链接 : https://leetcode.cn/problems/ugly-number-ii/
dp[i]：保存数据
[i2]:x2的指针
[i3]:x3的指针
[i5]:x5的指针
f0 就是现有子集 *2 *3 *5运算得到后续结果
f1 动态规划
package class066;
// 丑数 II
// 给你一个整数 n ，请你找出并返回第 n 个 丑数
// 丑数 就是只包含质因数 2、3 或 5 的正整数
// 测试链接 : https://leetcode.cn/problems/ugly-number-ii/
public class Code05_UglyNumberII {
// 时间复杂度O(n)，n代表第n个丑数
public static int nthUglyNumber(int n) {
// dp 0 1 2 ... n
// 1 2 ... ?
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2, i2 = 1, i3 = 1, i5 = 1, a, b, c, cur; i <= n; i++) {
a = dp[i2] * 2;
b = dp[i3] * 3;
c = dp[i5] * 5;
cur = Math.min(Math.min(a, b), c);
if (cur == a) {
i2++;
}
if (cur == b) {
i3++;
}
if (cur == c) {
i5++;
}
dp[i] = cur;
}
return dp[n];
}
}code6 32. 最长有效括号
// 最长有效括号
// 给你一个只包含 ‘(’ 和 ‘)’ 的字符串
// 找出最长有效（格式正确且连续）括号子串的长度。
// 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
dp[i]：以s[i]结尾构成的最长有效括号的长度
=0,s[i]= =‘(’
=dp[p-1]+dp[i-1]+2 s[p]= =‘(’&&s[i]==‘)’
p=i-dp[i-1]-1
f 动态规划
package class066;
// 最长有效括号
// 给你一个只包含 '(' 和 ')' 的字符串
// 找出最长有效（格式正确且连续）括号子串的长度。
// 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
public class Code06_LongestValidParentheses {
// 时间复杂度O(n)，n是str字符串的长度
public static int longestValidParentheses(String str) {
char[] s = str.toCharArray();
// dp[0...n-1]
// dp[i] : 子串必须以i位置的字符结尾的情况下，往左整体有效的最大长度
int[] dp = new int[s.length];
int ans = 0;
for (int i = 1, p; i < s.length; i++) {
if (s[i] == ')') {
p = i - dp[i - 1] - 1;
// ? )
// p i
if (p >= 0 && s[p] == '(') {
dp[i] = dp[i - 1] + 2 + (p - 1 >= 0 ? dp[p - 1] : 0);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}code7 67. 环绕字符串中唯一的子字符串
// 环绕字符串中唯一的子字符串
// 定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串
// 所以 base 看起来是这样的：
// “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”
// 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现
// 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
dp[?] 以?结尾的子字符串的长度，?26个字母
ans=∑dp(0<=i<26)
f 动态规划
package class066;
// 环绕字符串中唯一的子字符串
// 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串
// 所以 base 看起来是这样的：
// "..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.."
// 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现
// 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
public class Code07_UniqueSubstringsWraparoundString {
// 时间复杂度O(n)，n是字符串s的长度，字符串base长度为正无穷
public static int findSubstringInWraproundString(String str) {
int n = str.length();
int[] s = new int[n];
// abcde...z -> 0, 1, 2, 3, 4....25
for (int i = 0; i < n; i++) {
s[i] = str.charAt(i) - 'a';
}
// dp[0] : s中必须以'a'的子串，最大延伸长度是多少，延伸一定要跟据base串的规则
int[] dp = new int[26];
// s : c d e....
// 2 3 4
dp[s[0]] = 1;
for (int i = 1, cur, pre, len = 1; i < n; i++) {
cur = s[i];
pre = s[i - 1];
// pre cur
if ((pre == 25 && cur == 0) || pre + 1 == cur) {
// (前一个字符是'z' && 当前字符是'a') || 前一个字符比当前字符的ascii码少1
len++;
} else {
len = 1;
}
dp[cur] = Math.max(dp[cur], len);
}
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += dp[i];
}
return ans;
}
}code8 940. 不同的子序列 II
// 不同的子序列 II
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
// 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
// 字符但不改变剩余字符相对位置的一个新字符串
// 例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/
f 动态规划
package class066;
// 不同的子序列 II
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
// 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
// 字符但不改变剩余字符相对位置的一个新字符串
// 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/
public class Code08_DistinctSubsequencesII {
// 时间复杂度O(n)，n是字符串s的长度
public static int distinctSubseqII(String s) {
int mod = 1000000007;
char[] str = s.toCharArray();
int[] cnt = new int[26];
int all = 1, newAdd;
for (char x : str) {
newAdd = (all - cnt[x - 'a'] + mod) % mod;
cnt[x - 'a'] = (cnt[x - 'a'] + newAdd) % mod;
all = (all + newAdd) % mod;
}
return (all - 1 + mod) % mod;
}
}