我想要一種算法來查找給定字符串中包含不重複字符的字符的最長子字符串。我可以想到一個O（n * n）算法，它考慮給定字符串的所有子字符串並計算非重複字符的數量。例如，考慮字符串「AABGAKG」，其中唯一字符的最長子字符串是5個字符長，其對應於BGAKG。如何找到沒有重複字符的最長子字符串？
任何人都可以提出一個更好的方法來做到這一點嗎？
謝謝
編輯：我想我無法正確地向他人解釋我的問題。你可以在子字符串中有重複的字符（這不是我們需要一個子字符串中的所有不同的字符，這是geeksforgeeks解決方案所做的）。我必須找到的東西是任何子字符串中不重複字符的最大數量（可能是某些字符重複的情況）。
爲如說字符串是AABGAKGIMN然後BGAKGIMN是解決方案。
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"
我RegEx是相當薄弱的，你能解釋這是如何工作的？ --thnx – RBarryYoung
如何：
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);
}
}
只能防止重複的相鄰字符。給定字符串「nobody」，它會將整個字符串報告爲沒有重複字符，但OP的所需輸出將是「body」。 –
根據帖子「說字符串是AABGAKGIMN，那麼BGAKGIMN是解決方案」。在這個「解決方案」中，G的是一樣的。 –
['getLongestSubstringNoRepeats（「AABGAKGIMN」）'似乎不會終止]（https://ideone.com/09hFZ8）。除此之外，我認爲你返回的長度有一個錯誤（可能是1或2）。而你返回的長度，而不是實際的字符串。 – Dukeling
令s爲給定的字符串，而n它的長度。
將f（i）定義爲在s [i]處以不同的字母結尾的s的最長的[連續]子字符串。這是獨特的和明確的。
爲每個i計算f（i）。這很容易從F到推斷（I-1）和s [I]：
解決您的問題的任何f（i）的最大長度（不一定是唯一的）。
您可以實現此算法以O（n * 26）時間運行，其中26是字母表中的字母數。
對於每開始 = 0 ...（n-1），嘗試將結束到最右邊的位置。
保留一個布爾型數組[26]來記住是否有任何字符已被使用。 目前假設我們結束（開始，結束）
爲開始+ 1，
現在我們檢查new（start，end）。總的複雜性是O（N）。
我最喜歡這個！它簡短，快速，簡單！我希望它能起作用，否則我不得不刪除我的評論。當我看到正則表達式解決方案時，我認爲他們已經錯過了他們的SW-經驗或教育。 – AlexWien
公共靜態INT longestNonDupSubstring（燒焦[] 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;
}
這裏是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;
}
相當棘手的問題，我給你一個O基於C＃（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);
}
非常整潔的解決方案。 –
//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
}
請描述你正在努力達到什麼和怎麼做（避免使用像'97'這樣的魔術數字，特別是當有''''時）。您可以爲解決方案提供的時間複雜度最緊的限制是什麼？這個答案如何？有誰能提出一個更好的方法來做到這一點嗎？ – greybeard
其目前的形式漂亮題外話的問題，而是考慮如何可以在這裏使用一個'的std :: set'。 –
你可以使用散列表，並保持2個索引和一個計數器，想想它。你會得到它在O（n） – Omkant
這裏是你應該看到的鏈接，但我建議請嘗試自己解決首先... ........... http：//www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/ – Omkant