C++补充代码,输入只包含小写字母的非空字符串,长度小于100,寻找没有重复字母的子串,求这一类子串的最大长度并输出

#include <stdio.h>
#include <string.h>

int main() {
    char s[101];
    scanf("%s", s);
    int n = strlen(s);
    int ans = 0;
    int cnt[26] = {0}; // 存储每个字母出现的次数
    for (int i = 0; i < n; i++) {
        memset(cnt, 0, sizeof(cnt)); // 每次循环前清空计数器
        for (int j = i; j < n; j++) {
            if (cnt[s[j] - 'a'] == 1) {
                break; // 如果出现了重复字母，结束内层循环
            }
            cnt[s[j] - 'a']++;
            ans = ans > j - i + 1 ? ans : j - i + 1; // 更新答案
        }
    }
    printf("%d\n", ans);
    return 0;
}

相关问题

使用【c++】写【给定一个仅包含小写字母的字符串 s s，每次你可以选出一个回文子串，并将其删去；此时余下的字符串会自动前后拼接成一个新的字符串。 请问，最少需要多少步才能将原字符串全部删完？】的代码

在 C++ 中，解决这个问题可以采用动态规划的方法，尤其是使用 Manacher's Algorithm，这是一种用于寻找最短回文子串的高效算法。不过，由于题目允许删除任意回文子串，我们不需要使用这个专门的算法，可以直接遍历字符串并记录每个位置能够形成的最大回文子串长度。

以下是简单的步骤和代码实现：

1. 初始化两个变量 `max_len` 和 `center` 来存储当前已知的最大回文子串长度和它的中心位置。
2. 遍历输入字符串 `s`，对于每个字符 i：
- 计算左边界 `left[i]` 和右边界 `right[i]`，它们分别是从中心位置到 i 的最长回文子串的左右边界。
- 如果 `i + right[i] < s.size()`，则更新 `max_len` 和 `center`。
- 更新 `dp[i] = min(right[i], max_len)`，这是以字符 i 为中心的最长回文子串长度。
3. 最终答案就是字符串长度减去所有最长回文子串的总长度。

以下是相应的 C++ 代码示例：

#include <iostream>
#include <vector>

int main() {
    std::string s;
    // 输入只包含小写字母的字符串 s
    cin >> s;

    int n = s.size();
    std::vector<int> dp(n);
    int max_len = 0, center = 0;

    for (int i = 0; i < n; ++i) {
        if (i < center + max_len) {
            dp[i] = std::min(dp[2 * center - i], max_len - (i - center));
        } else {
            dp[i] = 1;
        }

        while (i - dp[i] >= 0 && i + dp[i] < n && s[i - dp[i]] == s[i + dp[i]]) {
            dp[i]++;
        }

        if (i + dp[i] > center + max_len) {
            center = i;
            max_len = dp[i];
        }
    }

    int steps = n - std::accumulate(dp.begin(), dp.end(), 0);

    std::cout << "最少需要 " << steps << " 步才能将原字符串全部删完。\n";
    return 0;
}

给定一字符串，请统计位置连续，且无重复字符出现的子串数量。例如abc是无重复字符的子串，abb不是。 注：内容一样但位置不一样的子串，按不同子串参与统计。 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串。 解答要求 时间限制: C/C++ 1000ms, 其他语言：2000ms 内存限制: C/C++ 256MB, 其他语言：512MB 输入 一个字符串，仅由小写英文字母组成，其长度范围：[1, 1000000] 输出 一个整数，表示统计出的无重复字符的子串的数量。 样例1 复制输入： abac 复制输出： 8 解释： 子串有 a、b、a、c、ab、ba、ac、aba、bac、abac, 无重复字符的子串为 a、b、a、c、ab、ba、ac、bac，因此统计结果为8。 样例2 复制输入： xbmxbnh 复制输出： 21 解释： 无重复字符的子串为 x、b、m、x、b、n、h、xb、bm、mx、xb、bn、nh、xbm、bmx、mxb、xbn、bnh、mxbn、xbnh、mxbnh，因此统计结果为21。

可以使用滑动窗口的思想来解决这个问题。定义两个指针 left 和 right，分别表示无重复字符子串的左右边界，初始值都为 0。然后不断地将 right 向右移动，直到发现第一个重复字符。此时，我们就可以得到一个以 left 为起点，right - 1 为终点的无重复字符子串。接着移动 left，直到刚刚那个重复字符从窗口中去除为止，然后再移动 right，如此往复，直到 right 到达字符串的末尾为止。

在这个过程中，我们使用一个哈希表来维护当前窗口中的所有字符及其出现的次数。具体地，哈希表中的每个键值对，都表示某个字符和其在窗口中出现的次数。每次移动 right 时，我们先将新的字符加入哈希表，然后判断当前窗口是否合法，如果不合法，则移动 left，并将哈希表中相应的字符出现次数减一，直到窗口再次合法为止。

最后，我们统计所有的合法子串的数量，即为所求的答案。

下面是具体的实现代码：