## Longest Substring Without Repeating Characters

May 16, 2011 in string

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Hint:
Is there a better way other than brute force? Consider the kind of data structure that can improve the run time complexity. An ideal solution requires only a one-time linear scan.

Online Judge
This problem is available at Online Judge. Head over there and it will judge your solution. Currently only able to compile C++ code. If you are using other languages, you can still verify your solution by looking at the judge’s test cases and its expected output.

Solution:
How can we can look up if a character had existed in the substring instantaneously? The answer is using a simple table to store the characters that have appeared. Make sure you communicate with your interviewer if the string can have characters other than ‘a’-'z’. (ie, Digits? Upper case letter? Does it contain ASCII characters only? Or even unicode character sets?)

As you traverse through the string, update by using its ASCII value as index to the table. If the string only contains ‘a’-'z’, you could save space by using a table of size 26 only. Assuming c is the character, then c-’a’ will give you a value of 0-25 which can be used to index the table directly.

The next question is to ask yourself what happens when you found a repeated character? For example, if the string is “abcdcedf”, what happens when you reach the second appearance of ‘c’?

When you have found a repeated character (let’s say at index j), it means that the current substring (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary. It also means that the repeated character must have appeared before at an index i, where i is less than j.

Since you know that all substrings that start before or at index i would be less than your current maximum, you can safely start to look for the next substring with head which starts exactly at index i+1.

Therefore, you would need two indices to record the head and the tail of the current substring. Since i and j both traverse at most n steps, the worst case would be 2n steps, which the run time complexity must be O(n).

Below is the implementation in C++. Beware of the common mistake of not updating the maximum after the main loop, which is easy to forget.

VN:F [1.9.22_1171]
Longest Substring Without Repeating Characters, 4.5 out of 5 based on 65 ratings

### 87 responses to Longest Substring Without Repeating Characters

1. A candidate:

#!/usr/bin/python

import collections

def problem(s):
….if len(s) == 0:
……..return ”

….h = set()
….r = collections.deque()
….longest = [None]

….def candidate():
……..if longest[0] == None or len(r) > len(longest[0]):
…………longest[0] = ”.join(r)

….for c in s:
……..# first character
……..if len(r) == 0:
…………r.append(c)
……..# a new character
……..elif c not in h:
…………r.append(c)
……..# a character we’ve seen, and is at the front
……..elif c in h and r[0] == c:
…………r.popleft()
…………r.append(c)

……..candidate()

….assert(longest[0] != None)
….return longest[0]

VA:F [1.9.22_1171]
0
2. My first thought was build a invert list first, and then hire interval tree to solve the possible overlaped intervals …

VA:F [1.9.22_1171]
0
3. I misunderstood the question, assumed that the substring wasn’t continuous. This one is simpler even.

#!/usr/bin/python

def substring(s):
i = 0
j = 0
h = set()
candidate = ”

while i < len(s):
while j len(candidate):
candidate = c

h.remove(s[i])
i += 1

return candidate

VA:F [1.9.22_1171]
-2
• if the substring didn’t have to be continuous it would be easy, you could just take 1 of each letter

VA:F [1.9.22_1171]
0
4. public class LongestSubString {
public static void main(String[] args) {

String str = “bbbb”;
String sb = “”;
for(int i=0;i<str.length();i++){
if(sb.indexOf(str.charAt(i)) == -1){
sb += str.charAt(i);
}
}

System.out.println("Substring: "+sb+" Length: " + sb.length());
}
}

VA:F [1.9.22_1171]
0
• HI Bala,

your above code fail test “abcbcbd”,here is bellow some modification code,its work correctly.

String str = “abcbcbd”;
String sb = “”;

for(int i=0;i<str.length();i++){

if(sb.indexOf(str.charAt(i)) == -1){
sb += str.charAt(i);
}
else
break;
}

System.out.println("Substring: "+sb+" Length: " + sb.length());

VA:F [1.9.22_1171]
0
5. the brute force solution is to use a two-level for loop. O(n^2)
By the help of heap, we can save some.

For current candidate sub-string S, the heaps saves both values and the related indices of each chars of S. S is identified by two pointers, p and q, for head and tail respectively. p is initialized to 0, so is q. Then advance q to the end.

When a next element comes, check the heap. If new, that is fine, move forward (also update a variable CURR which shows the current max length, if needed.)
If the value has been seen, say it’s index is r. do the following
(1) move p to r+1. anything between old p and r can be ignored.
(2) traverse the heap, delete any entry whose index is less than r.

When p is at the end, CURR is the answer.

VA:F [1.9.22_1171]
0
6. My solution keeps track of the last appearance of a char in a HashMap and the largest substring found so far.
If the current index has a repeated char, then a check if the current substring is greater than the largest I have so far. After, I restart the substring initial index and repeat the process.

VA:F [1.9.22_1171]
-3
7. Here is my code in C# O(n)
public class Pair
{
public int start { get; set; }
public int end { get; set; }
public int diff { get { return end – start; } }
}

public static Pair FindLongestNonRepetiveSubString(string str, int StartIndex, int CurrIndex)
{
Pair p = new Pair();
p.start = StartIndex;
p.end = CurrIndex-1;

for (int i = CurrIndex; i = StartIndex)
{

Pair x = FindLongestNonRepetiveSubString(str, oldIndex + 1, i + 1);
if (x.diff > p.diff)
p = x;
}
break;
}
else
{
p.end = i;
}

}

return p;

}

VA:F [1.9.22_1171]
0
8. #include
#include
using namespace std;

int main() {

char input[] = “abcabc”;

struct {
unsigned int charExists : 1;
} charIndex [256 ];

size_t indexMaxString, countMaxString, startIndex, interimCount, currentIndex;

memset ( charIndex, 0, sizeof(charIndex ));
indexMaxString = countMaxString = interimCount = currentIndex = startIndex =0;

for ( currentIndex = 0 ; currentIndex < strlen(input) ; ++currentIndex )
{
if(!charIndex[input[currentIndex]].charExists)
{
interimCount++;
charIndex[ input[currentIndex] ].charExists = 1;
}
else
{
if( countMaxString < interimCount )
{
indexMaxString = startIndex;
countMaxString = interimCount;
}
startIndex++;
}
}

if( countMaxString < interimCount )
{
indexMaxString = startIndex;
countMaxString = interimCount;
}
cout<<"The longest substring is : ";
cout.write(&input[indexMaxString], countMaxString);
cout<<endl;
return 0;
}

VA:F [1.9.22_1171]
0
9. Hmm.. i think most of the solution uses hashtable or some other ways to find the duplicates.. and some solutions doesn’t care about the contiguous property of a substring..

The longest substring should be contiguous!!..

Check here: An Algorithm a day
For a O(n) and O(1) space usage.

It will work without harm for large strings inside which we need to find the longest substring.

VA:F [1.9.22_1171]
0
• Your method is indeed NOT O(1) space algorithm. You assumed alphabet set to be [a-z] only. What if the alphabet is unicode char set? If the specification says that [a-z] is the ONLY possible inputs, then the solution posted here using O(1) space as well. It comes from the fact that O(26) = O(1).

Before providing a better solution, think more. In that way, you would find catches in your understanding. No offense pls.

VA:F [1.9.22_1171]
0
• Yeah.. you are right Mr. anonymous ..

I assumed to make it work only within [a-z] lower case characters.. Only less than 31 symbols max can be worked out with that approach.. So does that mean, without O(n) space, finding duplicates is not possible atall (with O(n) time obviously) ?

VA:F [1.9.22_1171]
0
10. The algorithm in the description is correct. But the code is not correct.
“Since you know that all substrings that start before or at index i would be less than your current maximum, you can safely start to look for the next substring with head which starts exactly at index i+1.”
But the code is “while (s[i] != s[j]) { exist[s[i]] = false; i++; } i++; j++; “. This in fact starts the new head at j+1 not i+1.

VA:F [1.9.22_1171]
0
• In fact, in the code the head “i” (not the iterator i) is not saved anywhere at all.

VA:F [1.9.22_1171]
0
• My idea is opposite to yours: the code is right, but the description is not precise. Below code means when we are sure all substring that start before or at index i would be less than our current maximum, we can safely move the start index i to the first appearance of character s[j] in face, by skipping all items between j and first j:

VA:F [1.9.22_1171]
+1
11. I have a C# one:

private int maxLengthOfSubstring(string s, out string subString)
{
int maxLength;

if (string.IsNullOrEmpty(s))
{
maxLength = 0;
subString = “N/A”;
}
else
{
// this will remove all the whitespaces inside the string
//char[] characters = s.Replace(” “, “” ).ToCharArray();
char[] characters = s.ToCharArray();
subString = characters[0].ToString();
maxLength = 1;

for (int i = 1; i < characters.Length; i++)
{
if (subString.Contains(characters[i].ToString()))
{
continue;
}
else
{
subString = subString + characters[i].ToString();
maxLength++;
}
}
}
return maxLength;
}

VA:F [1.9.22_1171]
0
12. This can be done using a simple iterating variable j.
The trick is to use the “exist” array to save the latest position when a character is visited, e.g., exist['a'] = 1 means ‘a’ is at index 1.
The inner while loop can be eliminated as we can determine if a character is in our current sub-string by comparing i with exist[s[j]]

int lengthOfLongestSubstring(string s) {
int n = s.length();
int i = 0, j = 0;
int maxLen = 0;
int exist[256] = { -1 };
while (j i) {
maxLen = max(maxLen, j-i);
i = exist[s[j]];
j++;
} else {
exist[s[j]] = j;
j++;
}
}
maxLen = max(maxLen, n-i);
return maxLen;
}

VA:F [1.9.22_1171]
0
13. Thee is some bug in my previous code. Here is the correct one.

int lengthOfLongestSubstring(string s) {
int n = s.length();
int i = 0, j = 0;
int maxLen = 0;
int exist[256];
for (int k = 0; k < 256; k++)
exist[k] = -1;
while (j = i) {
maxLen = max(maxLen, j-i);
i = exist[s[j]]+1;
exist[s[j]]=j;
j++;
} else {
exist[s[j]] = j;
j++;
}
}

maxLen = max(maxLen, n-i);
return maxLen;
}

VA:F [1.9.22_1171]
0

int is_there(char a,string temp,int s,int e)
{
for(int i=s; i<=e; i++)
{
if(a==temp[i])
return i;
}
return -1;
}

int lengthOfLongestSubstring(string s)
{
int st=0;
int en=-1;
int max=0;
int index=0;
int new_m;
for(int i=0; i<s.size(); i++)
{
index=is_there(s[i],s,st,en);
if(index<0)
{
en=i;
new_m=(en-st)+1;
if(max<new_m)
max=new_m;
}
else
{

st=index+1;
en=i;
new_m=(en-st)+1;
if(max<new_m)
max=new_m;

}

}
return max;
}

VA:F [1.9.22_1171]
0
15. one nit in the code:

s[i] is of type char, which ranges from -128 to 127, thus using it
directly as array index would cause problems when string s contains
charaters with negative values. It’s better to use s[i]+128 to fold the
range to [0, 255]

VA:F [1.9.22_1171]
0
16. here is a java solution to the problem

import java.util.*;
public class longestUniqueSubstring {
public static void main(String args[]){
String output = UniqueSubstring(input);
System.out.println(“input string is “+input);
System.out.println(“output string is “+output);
}
public static String UniqueSubstring(String input){
String maxSubstring = “”;
String ret = “”;
for(int i =0; i<input.length();i++){
boolean check = temp.containsKey(Character.toString(input.charAt(i)));
if (check == false) {
temp.put(Character.toString(input.charAt(i)),Character.toString(input.charAt(i)));
ret = ret + input.charAt(i);
}
else{
if(maxSubstring.length()<ret.length()) maxSubstring = ret;
int j = 0;
while(ret.charAt(j)!= input.charAt(i)){
temp.remove(Character.toString(ret.charAt(j)));
j++;
}
int pl = ret.indexOf(input.charAt(i));
ret = ret.substring(pl+1)+ input.charAt(i);
}
}
return maxSubstring;
}
}

VN:F [1.9.22_1171]
+2
17. A lot of people forget to ignore hash table entries of characters that are not in the current substring.
My solution uses a hash table to store the index of a character.

void findMaxSubstring(char const * str)
{
int maxSubstringLength = 0, maxSubstringStart = 255, maxSubstringEnd = 255;
int substringStartIndex = 0;
int substringEndIndex = 0;
int currentSubstringLength = 0;
unsigned char asciiHash[256];
memset(&asciiHash, 255, 256);
while(str[substringEndIndex] != ”)
{
if(asciiHash[str[substringEndIndex]] == 255 ||
asciiHash[str[substringEndIndex]] < substringStartIndex
)
{
//cout < maxSubstringLength)
{
maxSubstringLength = currentSubstringLength;
maxSubstringStart = substringStartIndex;
}
substringStartIndex = asciiHash[str[substringEndIndex]] + 1;
}
asciiHash[str[substringEndIndex]] = substringEndIndex;
substringEndIndex++;
}
currentSubstringLength = substringEndIndex – substringStartIndex;
if(currentSubstringLength > maxSubstringLength)
{
maxSubstringLength = currentSubstringLength;
maxSubstringStart = substringStartIndex;
}

cout << "printingSolution\n" << maxSubstringStart << " " << maxSubstringLength << "\n";
for(int i = maxSubstringStart ; i < maxSubstringStart + maxSubstringLength; i++)
{
cout << str[i];
}

}

VA:F [1.9.22_1171]
0
18. Abhishek, nice java code, thanks

VA:F [1.9.22_1171]
0
19. int lengthOfLongestSubstring(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
bool status[256] = { false };
int i = 0;
int j = 0;
int n = s.length();
int length = 0;
int max = 0;
while( i max )
max = length;
}
}
return max;
}

VN:F [1.9.22_1171]
0
20. sorry, paste failed.

int lengthOfLongestSubstring(string s)
{

}

VN:F [1.9.22_1171]
0
21. int lengthOfLongestSubstring(string s)
{
int i = 0;
int j = 0;
int n = s.length();
int length = 0;
int max = 0;
bool status[256] = { false };
while( i max )
max = length;
}
}
return max;
}

VN:F [1.9.22_1171]
0
22. In the if block, the ‘i++’ should not be there. In the next unique string we are going to check , the second occurrence of the character must be included.

VA:F [1.9.22_1171]
0
unsigned char e[26];
int p = 0, max = 0, b =0;
memset(e, 0, 26);

while(p<strlen(s))
{
if(e[s[p]-'a'] == 0)
{
e[s[p]-'a'] ++;
p++;
}
else
{

max = MAX (max,(p-b));
b = p;
memset(e, 0, 26);
}
}
max = MAX (max,(p-b));

printf("s:%s\nmax:%d\n",s,max);

VA:F [1.9.22_1171]
0
24. nicely explained..

VN:F [1.9.22_1171]
0
25. I think the solution may miss the case that s sub-string followed by consecutive chars.
e.g.
in: a-b-e-f-a-a-x-y
^ ^
out: efaaxy

VA:F [1.9.22_1171]
0
26. how about a simple dp algorithm

DP[i] –> length of the longest substring ending at position i

DP[i] = DP[i-1] + 1 if Arr[i-1] != Arr[i]
DP[i] = 1 otherwise

VA:F [1.9.22_1171]
0
• oops mine will return ‘bab’ as a valid string, a simple correction is your array charList[256[ at each loc we store the index of its occurence in the current substring, if ith char has already occured in the current substring , we need to find its occurence and the new substring can start from the loc’ + 1 and we update the ith char location array to i

VA:F [1.9.22_1171]
0
27. int longestSubstr( char str[], int len )
{
int charMap[26] = {0};
int length = 0;
int maxLen = 0;
for (int i = 0; i < len;++i)
{
int index = str[i]-'a';
if(charMap[index] == 0)
{
charMap[index] = 1;
++length;
}
else
{
memset(charMap,0,26);
if(maxLen< length)
maxLen = length;
length = 0;
}
}
return maxLen;
}

VA:F [1.9.22_1171]
0
28. how i can find all the longest substrings but not the length

VA:F [1.9.22_1171]
0
29. VN:F [1.9.22_1171]
0
30. VN:F [1.9.22_1171]
0
31. Thanks Leetcode.

My idea is to use the exsiting to store pointer (latest position of a char) instead of a boolean, so the inner while is not needed:

VA:F [1.9.22_1171]
0
32. VA:F [1.9.22_1171]
0
33. O(N) solution for the problem using O(N) space is possible. below link has the explanation and complete java code
http://www.dsalgo.com/2013/02/AllUniqueSubstring.php.html

VA:F [1.9.22_1171]
0
34. int LongestNRCS(string str)
{
if(str.length() < 2)
return str.length();

map charMap;
map::iterator it;
int maxLength = 0;
int length = 0;
for(int i = 0; i second;
it->second = i;
}

if(length > maxLength)
{
maxLength = length;
}
}

cout<<maxLength<<"\n";
return maxLength;
}

VA:F [1.9.22_1171]
0
35. import java.util.*;
public class Interpreter {
public static void main(String[] args) {
// Start typing your code here…
System.out.println(“Hello world!”);
System.out.println(“length is “+ findLength(“abcabcbb”));

}
public static int findLength(String s) {
TreeSet set = new TreeSet();
for(int i = 0; i<s.length(); i++) {
}
return set.size();
}
}

VN:F [1.9.22_1171]
0
36. package sy;

import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.OutputStream;
import java.io.PipedInputStream;
import java.net.URL;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
import javax.swing.text.html.HTMLDocument;

import com.sun.accessibility.internal.resources.accessibility;
import com.sun.org.apache.bcel.internal.generic.NEW;

public class SmallestSeq {
public static void main(String[] args) {
abd(“abcdefgdakzxvnmlopdsl”);
}
public static void abd(String input)
{
String result=”";
int start=0;
int maxLen=0;
int buffer[]=new int[256];
for (int i = 0; i < buffer.length; i++)
buffer[i]=-1;
for (int i = 0; i < input.length(); i++) {
if(buffer[input.charAt(i)]==-1)
{
buffer[input.charAt(i)]=10;

}
else
{
if(maxLen<i-start)
{
maxLen=i-start;
result=input.substring(start, i);
}
while(start<i)
{
buffer[input.charAt(start)]=-1;
start++;
}
}
}
System.out.println(result);
}
}

VN:F [1.9.22_1171]
0
37. Solution in java. ‘result’ array keeps tracking the start and end point of the substring with max length.

VN:F [1.9.22_1171]
0
• The ` tag ignore some characters in the last solution... Here is the correct one. public class Solution { public int lengthOfLongestSubstring(String s) { // Start typing your Java solution below // DO NOT write main() function if(s.length() == 0){ return 0; } char [] charArray = s.toCharArray(); int [] result = new int[2]; int [] asciiTab = new int[128]; // assume the chars all come from ascii table Arrays.fill(asciiTab, -1); int i,j; //i: start index of substring; j: end index of substrin i = 0; result[0] = i; result[1] = i+1; asciiTab[charArray[i]] = i; for(j=1;j= i){ // found a char that has been discovered // in the range of substring current discovering if(result[1]-result[0] charArray.length-1) // i hit the end of the string break; }`

` if(j==charArray.length-1){ // j hit the end of the string if(result[1]-result[0] < j-i+1){ result[0] = i; result[1] = j+1; } }`

` asciiTab[charArray[j]] = j; // update bookkeeping`

` } return (result[1]-result[0]); } }`

VN:F [1.9.22_1171]
0
• public class Solution {
public int lengthOfLongestSubstring(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s.length() == 0){
return 0;
}
char [] charArray = s.toCharArray();
int [] result = new int[2];
int [] asciiTab = new int[128]; // assume the chars all come from ascii table
Arrays.fill(asciiTab, -1);
int i,j; //i: start index of substring; j: end index of substrin
i = 0;
result[0] = i;
result[1] = i+1;
asciiTab[charArray[i]] = i;
for(j=1; j= i){
// found a char that has been discovered
// in the range of substring current discovering
if(result[1]-result[0] charArray.length-1) // i hit the end of the string
break;
}

if(j==charArray.length-1){ // j hit the end of the string
if(result[1]-result[0] < j-i+1){
result[0] = i;
result[1] = j+1;
}
}

asciiTab[charArray[j]] = j; // update bookkeeping

}
return (result[1]-result[0]);
}
}

VN:F [1.9.22_1171]
0
• omg, why are characters in for loop is always ignored!!!
should be ‘for(j=1; j<charArray.length; j++)'

VN:F [1.9.22_1171]
0
• last try….

VN:F [1.9.22_1171]
0
38. VN:F [1.9.22_1171]
0
• Fixed version

VN:F [1.9.22_1171]
0
39. <?php
\$rest = substr("abcdef", , );
echo "\$rest”;
?>
without start length and size of length of string in php

VA:F [1.9.22_1171]
0
40. superb！

VN:F [1.9.22_1171]
0
41. This is showing correct ouput in my IDE but is showing output limit exceeded on Online Judge here.

VN:F [1.9.22_1171]
0
42. VN:F [1.9.22_1171]
0
43. VN:F [1.9.22_1171]
0
44. Sorry for previous wrong post with missing part.

VN:F [1.9.22_1171]
0
45. Part of the code is striped by the \` tag... wired Need to add the following statement at the end of the for loop. for(int i=0; imax){ max = j; } } return max; } }`

VN:F [1.9.22_1171]
0
46. public class Solution {
public int lengthOfLongestSubstring(String s) {
// Start typing your Java solution below
// DO NOT write main() function
HashSet hs = new HashSet();
int l = s.length();
int i=0;
int j=0;
int max = 0;
while(j<l){
if(hs.contains(s.charAt(j))){
max = Math.max(max, j-i);
while(s.charAt(i)!=s.charAt(j)){
hs.remove(s.charAt(i));
i++;
}
i++;
j++;

}
else{
j++;
}
}
return Math.max(max, l-i);
}
}

VN:F [1.9.22_1171]
0
47. How about the input is “abcadef” ? The current solution gives 3 (abc or def), but it should be 6 “bcadef”.

VN:F [1.9.22_1171]
0
48. int lstr(string str){
int exist[256];
for (int i = 0; i<256; ++i){
exist[i] = 0;
}
int maxLength = 0;
for(int i = 0; i < str.size(); ++i)
{
if (exist[str[i]])
{
maxLength = max(i – exist[str[i]], maxLength);
}
exist[str[i]] = i;
}
return maxLength;
}

VA:F [1.9.22_1171]
0
49. The official approach in the question is wrong
for example abcdefgcihjklmnopqrstuvwxyz

it will return ihjklmnopqrstuvwxyz, actually it should be defgcihjklmnopqrstuvwxyz

VN:F [1.9.22_1171]
0
50. Here is my code ( a single for loop – that prints all possible continuous substrings of no repeating characters ) in Java !

VN:F [1.9.22_1171]
0
51. Here is the code for getting all possible longest continuous substrings in Java !:

VN:F [1.9.22_1171]
0
• I don’t know why the

doesn’t work properly…some of the code is missing above..but I think you guys got the logic…

VN:F [1.9.22_1171]
0
52. Hi 1377coder,

could you please explain the following code snippet:

VA:F [1.9.22_1171]
0
53. VN:F [1.9.22_1171]
0
54. That’s a really elegant solution! Thanks a lot!

VN:F [1.9.22_1171]
0
55. char* lengthOfLongestSubstring(char a[])
{
char *p1,*p2;
p1=a;
int i=0;
char static visitarr[256]={NULL};
bool matchfound=false;
visitarr[0]=*p1;
p2=visitarr;
while(*p1)
{
do
{
if(*p1==*p2)
{
matchfound=true;

break;
}
} while (*p2++);

if(!matchfound)
visitarr[++i]=*p1;

p2=visitarr;
matchfound=false;
p1++;
}

return visitarr;
}

VN:F [1.9.22_1171]
0
56. VA:F [1.9.22_1171]
0
57. String str = “abcbcbd”;
String sb = “”;

for(int i=0;i<str.length();i++){

if(sb.indexOf(str.charAt(i)) == -1){
sb += str.charAt(i);
}
else
break;
}

System.out.println("Substring: "+sb+" Length: " + sb.length());

VA:F [1.9.22_1171]
0
58. how about such compact solution?

VN:F [1.9.22_1171]
0
59. you can make it more efficient by changing the boolean[] to int[]

VN:F [1.9.22_1171]
0
60. Here is a java code. Tested.

VA:F [1.9.22_1171]
0
61. What is the ans for this case?
“wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco”
ans : 10 ?

VA:F [1.9.22_1171]
0
62. huz said on May 17, 2014

A scala version, any better idea for Map[Char, Int]

VA:F [1.9.22_1171]
0
63. Hi all,

I have doubt about this “When you have found a repeated character (let’s say at index j), it means that the current substring (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary.”, I think a repeated character doesn’t mean a potential maximum, precisely speaking, a character with its last occurrence index less than i makes a potential maximum. If we initialize the index-recording table to all -1s, a new character also falls into this situation, since a first-time-occurrence character’s last occurrence index is -1.

P.S. thanks for building up this website and the comments from different users. I really enjoy reading all of your brilliant ideas.

VN:F [1.9.22_1171]
0
64. To support my above discussion, here is my code in Java.

VN:F [1.9.22_1171]
0
• well, it’s eating my code… for the second for loop, the first few lines should be:

for (int j = 0; j = i) {
// find a repeating char in the range from i to j – 1,
// this won’t give us a new maximum, all we need to do is updating the i.
i = table[currentChar - 'a'] + 1;
}

VN:F [1.9.22_1171]
0
• well well, it’s still eating my code… the loop is basically iterate through the charArray, for each character, I call it currentChar, if table[currentChar - 'a'] is greater than or equal to i, only update the i as i = table[currentChar - 'a'] + 1; if not, go to that else block, the code there is fine.

Hopefully, at least, I didn’t confuse you guys.

VN:F [1.9.22_1171]
0
65. 15-line codes:

VA:F [1.9.22_1171]
0
66. if you want to return the actual string, try this

` #include #include #include #include`

`using namespace std;`

`string longestsubstr(string given){ set myset; vector vec; int start= 0; int end = 0; stringstream ss; set::iterator it; while(end != given.length()){`

` it = myset.find(given.at(end)); if(it!=myset.end()){ myset.insert(given.at(end)); }else{ vec.push_back(given.substr(start, end-start)); for(int i = start; i != end; i++){ if(given.at(i) == given.at(end)){ start = i+1; break; } myset.erase(given.at(i)); } } end++; } vec.push_back(given.substr(start, end-start)); string s = ""; for(vector::iterator it = vec.begin(); it!= vec.end(); it++){ if(it->length()>s.length()) s= *it; } return s; }`

`int main() { cout << "Hello World" << endl; cout<<longestsubstr("zabcabdefa")<<endl; return 0; } `

VA:F [1.9.22_1171]
0
• the missing includes are “iostream”, “set”, “vector” and “sstream”

VA:F [1.9.22_1171]
0
• let me try again

VA:F [1.9.22_1171]
0
67. #include
#include
#include
main()
{
int t;
scanf(“%d”,&t);
while(t–){
char c[100001],ar[100001];int l,i,j,pos=-1,cnt=1,cur=1,max=1,x;
scanf(“%s”,c);fflush(stdin);
ar[0]=c[0];
l=strlen(c);
for(i=1;i<l;i++)
{
x=0;
for(j=pos+1;j<cnt;j++)
{
if(c[i]!=ar[j])
x++;
else if(c[i]==ar[j])
pos=j;
}
if(x==cnt)
{
ar[cnt++]=c[i];
cur=cnt;
}
else
{
ar[cnt++]=c[i];
if(cur<cnt-(pos+1))
{
cur=cnt-(pos+1);
}
}
if(max<cur)
{
max=cur;
}
}
printf("%d\n",max);
}
}

VA:F [1.9.22_1171]
0