用 C++4.8.1版本代码实现 输入一个仅由可见字符组成的字符串 s。现在要求从中找出一个连续的最长子串,保证这个子串每一位字符都不相同。如果找到多个长度相同的子串,请输出字典序最大的。
时间: 2024-02-21 18:59:13 浏览: 159
以下是 C++ 代码实现:
```c++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
char s[MAXN];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1), ans_len = 0, ans_pos = 0;
int l = 1, r = 0;
unordered_map<char, int> mp;
while (r < n) {
while (r < n && mp[s[r + 1]] < 1) {
mp[s[++r]] = 1;
}
if (r - l + 1 > ans_len) {
ans_len = r - l + 1;
ans_pos = l;
} else if (r - l + 1 == ans_len) {
ans_pos = max(ans_pos, l);
}
mp[s[l++]]--;
}
for (int i = ans_pos; i < ans_pos + ans_len; i++) {
printf("%c", s[i]);
}
printf("\n");
return 0;
}
```
代码思路:
使用双指针法,维护一个区间 $[l,r]$,表示当前处理的子串。使用 unordered_map 统计当前子串中每个字符出现的次数,如果出现次数大于等于 $2$,则不断右移左指针 $l$,直到当前子串中不含有重复的字符。在维护过程中,同时记录最长子串的长度和起始位置,如果找到了一个长度相同的子串,则选择字典序最大的输出。
时间复杂度为 $O(n)$。
注意:该代码使用了 unordered_map,需要使用 -std=c++11 编译。如果你的编译器不支持 unordered_map,可以使用 map 代替,但是时间复杂度会有所增加。
阅读全文