C++求解无重复字符的最长子串 |21xrx.com

C++求解无重复字符的最长子串

2023-07-09 16:26:21 深夜i -- --

C++ 无重复字符最长子串求解

在字符串中，一个子串是指字符串中连续的一段字符组合而成的子集。无重复字符的子串指在一个子串中，每个字符只出现一次。对于给定的字符串，我们希望找出它的最长的无重复字符的子串。

使用C++可以方便地实现这个问题的求解。以下是一个简单的算法，它可以找到一个字符串的最长无重复字符的子串。

1. 使用访问过的字符的集合和两个指针：起始指针和结束指针。

2. 起始指针指向字符串的开头，结束指针指向字符串的第一个字符。

3. 从结束指针开始，逐一添加每个字符，直到遇到重复的字符或者到达字符串的末尾。

4. 在结束指针到达字符串的末尾时，计算当前子串的长度。

5. 如果当前子串长度大于之前找到的最长子串的长度，则更新最长子串的信息。

6. 如果当前子串中出现了重复字符，移动起始指针直到移除掉重复字符为止。移动指针的同时，从访问过的字符的集合中删除已经移除的字符，以便能够添加新的字符。

7. 重复步骤3到6，直到结束指针到达字符串的末尾。

下面是这个算法的C++实现:


#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int findLongestSubstring(string s) {
  int start = 0, end = 0, maxLength = 0;
  unordered_set<char> visited;
  while (end < s.length()) {
    if (visited.count(s[end]) == 0) {
      visited.insert(s[end++]);
      maxLength = max(maxLength, end - start);
    }
    else {
      visited.erase(s[start++]);
    }
  }
  return maxLength;
}
int main() {
  string s = "pwwkew";
  int maxLength = findLongestSubstring(s);
  cout << "The longest substring without repeating characters of " << s << " is " << maxLength << endl;
  return 0;
}

在这个C++代码中，我们使用了一个unordered_set来记录访问过的字符。end指针从0开始，每次循环向后移动一个位置。如果添加当前字符后出现重复字符，则移动start指针，直到出现不重复的字符为止。

这个算法的时间复杂度是O(n)，因为每个字符被访问了一次，空间复杂度也是O(n)，因为最多需要保存n个不同的字符。

总结

最长无重复字符的子串是一个常见的字符串问题，它可以用C++实现一个简单的算法。该算法的时间复杂度和空间复杂度都是O(n)，是一个非常高效的解决方法。在实际应用中，当我们需要处理带有许多不同字符的字符串时，这个算法可以帮助我们快速识别出其中的重复字符，从而保证程序的正确性和效率。

上一篇: idea打包java可执行jar包

下一篇: 「VC++6.0编译指南」

评论区

()

相似文章