string - 如何找到最长的不重复字符的子串？

Question

我想要一种算法来查找给定字符串中不包含重复字符的最长字符子字符串。我可以想到一个 O(n*n) 算法，它考虑给定字符串的所有子字符串并计算非重复字符的数量。例如，考虑字符串“AABGAKG”，其中唯一字符的最长子字符串为 5 个字符长，对应于 BGAKG。

谁能提出更好的方法？

谢谢

编辑:我想我无法向其他人正确解释我的问题。您可以在子字符串中包含重复字符(这并不是说我们需要 geeksforgeeks 解决方案所做的子字符串中的所有不同字符)。我必须找到的是任何子字符串中非重复字符的最大数量(可能是某些字符重复的情况)。

例如，假设字符串是 AABGAKGIMN 那么 BGAKGIMN 就是解决方案。

Answer 1

对于每个 start = 0 ... (n-1)，尝试将 end 扩展到最右边的位置。

保留一个 bool 数组 used[26] 以记住是否有任何字符已被使用。 假设目前我们完成了(开始，结束)

对于开始+1，

• 首先清除集合:used[str[start]] = false;
• while ((end+1 < n) && (!used[str[end+1]])) { used[str[end+1]]=true;++结束；

现在我们已经检查了新的(开始，结束)。总复杂度为 O(N)。