【七十一】【算法分析与设计】467. 环绕字符串中唯一的子字符串,940. 不同的子序列 II,子串的划分,子序列的划分,区间划分---递推

467. 环绕字符串中唯一的子字符串

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

示例 1：

输入：s = "a" 输出：1 解释：字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入：s = "cac" 输出：2 解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入：s = "zab" 输出：6 解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。

提示：

1 <= s.length <= 10(5)

s 由小写英文字母组成

子串的划分,以某个位置结尾的子串,进行子串的划分.

把所有位置结尾的子串中出现在base个数记录下来即可.

只需要记录以某位置结尾往前最长的连续子串长度即可.

例如abcde,bcde,cde,de,e,最长的连续子串长度是5,依次对应五个数量.

子串的划分----分治

#include <bits/stdc++.h>  // 引入常用的头文件
using namespace std;

class Solution {
public:
    using ll = long long;  // 定义类型别名ll，表示长整型long long
    string s;              // 定义字符串s，存储输入字符串
    vector<ll> dp;         // 使用动态规划存储中间结果，dp[i]存储以s[i]结尾的子串的合法子串数量
    vector<ll> count;      // 记录每个字母为结束字符的最长子串长度

    // 初始化函数，清空并重设dp和count数组
    void solveinit() {
        dp.clear();                     // 清空dp数组
        dp.resize(s.size(), -1);        // 重设dp数组大小，初始值为-1
        count.clear();                  // 清空count数组
        count.resize(26);               // 重设count数组大小，大小为26（26个字母）
    }

    // 深度优先搜索函数，用于计算以第i个字符结束的子串的合法子串数量
    ll dfs(ll i) {
        if (dp[i] != -1)                // 如果dp[i]已计算过，直接返回结果
            return dp[i];
        if (i - 1 >= 0) {               // 如果不是第一个字符，可以考虑前一个字符
            if (s[i] != 'a') {          // 当前字符不是'a'时
                if (s[i - 1] == s[i] - 1) {  // 如果前一个字符正好是当前字符的前一个字母
                    dp[i] = dfs(i - 1) + 1;  // 递归计算前一个字符，并加上当前字符形成的新的子串
                } else {
                    dp[i] = 1;          // 否则，当前字符自成一组
                }
            } else {
                if (s[i - 1] == 'z') {  // 当前字符是'a'且前一个字符是'z'
                    dp[i] = dfs(i - 1) + 1;  // 递归计算前一个字符，并加上当前字符形成的新的子串
                } else {
                    dp[i] = 1;          // 否则，当前字符自成一组
                }
            }
        } else {
            dp[i] = 1;                  // 如果是第一个字符，只有当前字符自身一个子串
        }
        return dp[i];                   // 返回以s[i]结尾的合法子串数量
    }

    // 主函数，计算字符串s中有多少不同非空子串也在环绕字符串base中出现
    int findSubstringInWraproundString(string _s) {
        s = _s;                         // 存储输入字符串
        solveinit();                    // 初始化dp和count数组
        for (ll i = 0; i < s.size(); i++) {
            dfs(i);                     // 对每个字符调用dfs函数，计算以每个字符结尾的子串数量
        }

        ll ans = 0;
        vector<bool> visited(26);       // 标记数组，记录每个字符是否被访问过
        for (ll i = 0; i < s.size(); i++) {
            int index = s[i] - 'a';     // 当前字符对应的索引
            count[index] = max(count[index], dp[i]);  // 更新以当前字符结尾的最大子串数量
        }

        for (ll i = 0; i < 26; i++) {
            ans += count[i];            // 累加每个字母对应的最长子串数量
        }
        return ans;                     // 返回结果
    }
};

940. 不同的子序列 II

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc" 输出：7 解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba" 输出：6 解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa" 输出：3 解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

1 <= s.length <= 2000

s 仅由小写英文字母组成

假设s长度为n.

区间[0,n-1]的字符串的不同的子序列个数是多少.

区间[0,n-2]的字符串的不同的子序列个数是多少.

可以选择由[0,n-2]区间字符串的不同子序列个数多少推导出[0,n-1]的字符串的不同的子序列个数是多少.

因为新增的子序列是[0,n-2]区间所有子序列后面全部加上n-1位置的字符所组成的子序列加上n-1位置单独的字符子序列.

只需要完成新增子序列与老子序列的去重操作即可.

新增子序列都是以n-1位置结尾的子序列,一定是包含了所有的以n-1字符结尾的可能性.

所以老子序列中去掉以n-1字符结尾的可能性加上其他字符结尾的个数即可.

子序列的划分----分治

长度的划分,递推,增加的子序列很好计算.

class Solution {
public:
    using ll = long long; // 定义类型别名 ll，表示长整型 long long
    string s; // 用于存储输入的字符串
    vector<ll> count; // 使用一个数组来统计每个字符作为子序列结尾的不同子序列个数
    const ll MOD = 1e9 + 7; // 定义常量 MOD，取值为 10^9 + 7，用于结果的模运算

    void solveinit() {
        count.clear(); // 清空 count 数组
        count.resize(26); // 将 count 数组大小重新设置为26（对应26个英文字母）
    }

    int distinctSubseqII(string _s) {
        s = _s; // 将传入的字符串赋值给成员变量 s
        solveinit(); // 调用初始化函数，准备 count 数组
        for (ll i = 0; i < s.size(); i++) { // 遍历字符串 s 的每个字符
            ll all = 0; // 初始化 all 变量，用来统计到当前字符为止的所有可能子序列的数量
            for (ll j = 0; j < count.size(); j++) { // 遍历 count 数组，累加之前所有字符的子序列总数
                all = (all + count[j]) % MOD; // 将累加结果进行模运算，防止溢出
            }
            ll index = s[i] - 'a'; // 计算当前字符在 count 数组中的索引位置
            count[index] = (all + 1) % MOD; // 更新当前字符的子序列数。加1是因为当前字符本身也是一个子序列
        }
        ll ans = 0; // 初始化答案变量，用来存储最终的不同子序列总数
        for (ll i = 0; i < count.size(); i++) { // 遍历 count 数组，将所有字符的子序列数累加
            ans = (ans + count[i]) % MOD; // 累加的同时进行模运算，防止溢出
        }
        return ans; // 返回最终计算的结果
    }
};