输入一个仅由可见字符组成的字符串 s。现在要求从中找出一个连续的最长子串,保证这个子串每一位字符都不相同。如果找到多个长度相同的子串,请输出字典序最大的。c++
时间: 2024-02-13 20:05:51 浏览: 103
找出一个字符串的最长子串
5星 · 资源好评率100%
可以使用滑动窗口的思想来解决这个问题。维护一个窗口,窗口中的字符都不相同,且窗口大小最大。当窗口右侧的字符与窗口内的某个字符相同时,将左侧的窗口边界移动到该相同字符的下一位。对于多个长度相同的子串,我们可以使用字典序最大的方式来选择。
以下是对应的 C++ 代码实现:
```c++
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
string longestSubstring(string s) {
int n = s.size();
if (n == 0) return "";
string res = "";
int start = 0, end = 0;
unordered_map<char, int> charMap;
while (end < n) {
char c = s[end];
if (charMap.find(c) != charMap.end() && charMap[c] >= start) {
start = charMap[c] + 1;
}
charMap[c] = end;
if (end - start + 1 > res.size() || (end - start + 1 == res.size() && s.substr(start, end - start + 1) > res)) {
res = s.substr(start, end - start + 1);
}
end++;
}
return res;
}
int main() {
string s = "abcabcbb";
string res = longestSubstring(s);
cout << res << endl; // expected output: "abc"
return 0;
}
```
阅读全文