我想要一种算法来查找给定字符串中不包含重复字符的最长字符子串。我可以想到一个 O(n*n) 算法，它考虑给定字符串的所有子字符串并计算非重复字符的数量。例如，考虑字符串“ AABGAKG ”，其中唯一字符的最长子字符串为 5 个字符，对应于BGAKG。
任何人都可以提出更好的方法吗？
谢谢
编辑：我认为我无法向其他人正确解释我的问题。您可以在子字符串中包含重复字符（这并不是说我们需要 geeksforgeeks 解决方案所做的子字符串中的所有不同字符）。我必须找到的东西是任何子字符串中的最大不重复字符（可能是某些字符重复的情况）。
例如，说字符串是AABGAKGIMN然后BGAKGIMN是解决方案。
对于每个start = 0 ... (n-1)，尝试将end扩展到最右边的位置。
保留一个 bool 数组 used[26] 以记住是否已经使用了任何字符。假设目前我们完成了（开始，结束）
对于开始+1，
现在我们检查了新的（开始，结束）。总复杂度为 O(N)。
这是 C# 中的解决方案。我在 Visual Studio 2012 中进行了测试，它可以工作
public static int LongestSubstNonrepChar(string str) {
int curSize = 0;
int maxSize = 0;
int end = 0;
bool[] present = new bool[256];
for (int start = 0; start < str.Length; start++) {
end = start;
while (end < str.Length) {
if (!present[str[end]] && end < str.Length)
{
curSize++;
present[str[end]] = true;
end++;
}
else
break;
}
if (curSize > maxSize) {
maxSize = curSize;
}
//reset current size and the set all letter to false
curSize = 0;
for (int i = 0; i < present.Length; i++)
present[i] = false;
}
return maxSize;
}
这个怎么样：
public static String getLongestSubstringNoRepeats( String string ){
int iLongestSoFar = 0;
int posLongestSoFar = 0;
char charPrevious = 0;
int xCharacter = 0;
int iCurrentLength = 0;
while( xCharacter < string.length() ){
char charCurrent = string.charAt( xCharacter );
iCurrentLength++;
if( charCurrent == charPrevious ){
if( iCurrentLength > iLongestSoFar ){
iLongestSoFar = iCurrentLength;
posLongestSoFar = xCharacter;
}
iCurrentLength = 1;
}
charPrevious = charCurrent;
xCharacter++;
}
if( iCurrentLength > iLongestSoFar ){
return string.substring( posLongestSoFar );
} else {
return string.substring( posLongestSoFar, posLongestSoFar + iLongestSoFar );
}
}
相当棘手的问题，我给你一个基于 C# 的 O(n) 解决方案。
公共字符串 MaxSubStringKUniqueChars（字符串源，int k）{
if (string.IsNullOrEmpty(source) || k > source.Length) return string.Empty;
var start = 0;
var ret = string.Empty;
IDictionary<char, int> dict = new Dictionary<char, int>();
for (var i = 0; i < source.Length; i++)
{
if (dict.ContainsKey(source[i]))
{
dict[source[i]] = 1 + dict[source[i]];
}
else
{
dict[source[i]] = 1;
}
if (dict.Count == k + 1)
{
if (i - start > ret.Length)
{
ret = source.Substring(start, i - start);
}
while (dict.Count > k)
{
int count = dict[source[start]];
if (count == 1)
{
dict.Remove(source[start]);
}
else
{
dict[source[start]] = dict[source[start]] - 1;
}
start++;
}
}
}
//just for edge case like "aabbcceee", should return "cceee"
if (dict.Count == k && source.Length - start > ret.Length)
{
return source.Substring(start, source.Length - start);
}
return ret;
}
`
//这是测试用例。
public void TestMethod1()
{
var ret = Item001.MaxSubStringKUniqueChars("aabcd", 2);
Assert.AreEqual("aab", ret);
ret = Item001.MaxSubStringKUniqueChars("aabbccddeee", 2);
Assert.AreEqual("ddeee", ret);
ret = Item001.MaxSubStringKUniqueChars("abccccccccaaddddeeee", 3);
Assert.AreEqual("ccccccccaadddd", ret);
ret = Item001.MaxSubStringKUniqueChars("ababcdcdedddde", 2);
Assert.AreEqual("dedddde", ret);
}
公共静态intlongestNonDupSubstring（char [] str）{
int maxCount = 0;
int count = 0;
int maxEnd = 0;
for(int i=1;i < str.length;i++) {
if(str[i] != str[i-1]) {
count++;
}
if (str[i] == str[i-1]) {
if(maxCount<count) {
maxCount = count;
maxEnd = i;
}
count = 0;
}
if ( i!=str.length-1 && str[i] == str[i+1]) {
if(maxCount<count) {
maxCount = count - 1;
maxEnd = i-1;
}
count = 0;
}
}
int startPos = maxEnd - maxCount + 1;
for(int i = 0; i < maxCount; i++) {
System.out.print(str[startPos+i]);
}
return maxCount;
}
让 s 是给定的字符串，n 是它的长度。
将 f(i) 定义为 s 的最长 [连续] 子字符串，以 s[i] 结尾且具有不同的字母。这是独特的和明确的。
计算每个 i 的 f(i)。由 f(i-1) 和 s[i] 很容易推导出：
您的问题的解决方案是任何最大长度的 f(i)（不一定是唯一的）。
您可以实现此算法以在 O(n * 26) 时间内运行，其中 26 是字母表中的字母数。
让我也贡献一点。我有这个复杂的解决方案将是 O(N)。该算法的空间复杂度为 O(K)，其中 K 是输入字符串中不同字符的数量。
public static int NoRepeatSubstring(string str)
{
int start = 0;
int maxLen = 0;
Dictionary<char, int> dic = new Dictionary<char, int>();
for (int i = 0; i < str.Length; i++)
{
char rightChar = str[i];
// if the map already contains the 'rightChar', shrink the window from the beginning so that
// we have only one occurrence of 'rightChar'
if (dic.ContainsKey(rightChar))
{
// this is tricky; in the current window, we will not have any 'rightChar' after its previous index
// and if 'start' is already ahead of the last index of 'rightChar', we'll keep 'windowStart'
start = Math.Max(start, dic[rightChar] + 1);
}
if (dic.ContainsKey(str[i]))
dic[str[i]] = i;
else
dic.Add(str[i], i);
maxLen = Math.Max(maxLen, i - start + 1);
}
return maxLen;
}
这里有一些单元测试：
Assert.Equal(3, SlideWindow.NoRepeatSubstring("aabccbb"));
Assert.Equal(2, SlideWindow.NoRepeatSubstring("abbbb"));
Assert.Equal(3, SlideWindow.NoRepeatSubstring("abccde"));
//Given a string ,find the longest sub-string with all distinct characters in it.If there are multiple such strings,print them all.
#include<iostream>
#include<cstring>
#include<array>
using namespace std;
//for a string with all small letters
//for capital letters use 65 instead of 97
int main()
{
array<int ,26> count ;
array<string,26>largest;
for(int i = 0 ;i <26;i++)
count[i]=0;
string s = "abcdefghijrrstqrstuvwxyzprr";
string out = "";
int k = 0,max=0;
for(int i = 0 ; i < s.size() ; i++)
{
if(count[s[i] - 97]==1)
{
int loc = out.find(s[i]);
for(int j=0;j<=loc;j++) count[out[j] - 97]=0;
if(out.size() > max)
{
max = out.size();
k=1;
largest[0] = out;
}
else if(out.size()==max) largest[k++]=out;
out.assign(out,loc+1,out.size()-loc-1);
}
out = out + s[i];
count[s[i] - 97]++;
}
for(int i=0;i<k;i++) cout<<largest[i] << endl;
//output will be
// abcdefghijr
// qrstuvwxyzp
}
string MaximumSubstringNonRepeating(string text)
{
string max = null;
bool isCapture = false;
foreach (string s in Regex.Split(text, @"(.)\1+"))
{
if (!isCapture && (max == null || s.Length > max.Length))
{
max = s;
}
isCapture = !isCapture;
}
return max;
}
.匹配任何字符。( )捕捉到那个角色。\1再次匹配捕获的字符。+重复那个字符。整个模式匹配任何一个字符的两个或多个重复。"AA"或",,,,"。
Regex.Split()在模式的每次匹配时拆分字符串，并返回介于两者之间的片段数组。（一个警告：它还包括捕获的子字符串。在这种情况下，重复的一个字符。捕获将显示在片段之间。这是我刚刚添加isCapture标志的方式。）
该函数删除所有重复字符，并返回重复的每组重复字符之间的最长片段。
>>> MaximumSubstringNonRepeating("AABGAKG") // "AA" is repeated
"BGAKG"
>>> MaximumSubstringNonRepeating("AABGAKGIMNZZZD") // "AA" and "ZZZ" are repeated.
"BGAKGIMN"