# Longest Substring Without Repeating Characters

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]
Rating: 4.6/5 (96 votes cast)
Longest Substring Without Repeating Characters, 4.6 out of 5 based on 96 ratings

## 93 thoughts on “Longest Substring Without Repeating Characters”

1. Arni Mar

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 == None or len(r) > len(longest):
…………longest = ”.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 == c:
…………r.popleft()
…………r.append(c)

……..candidate()

….assert(longest != None)
….return longest

VA:F [1.9.22_1171]
0
2. tengteng

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. Arni Mar

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]
-4
1. asdfasdfasdf

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. bala

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]
+1
1. Charaling

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
1. delavior

Hi,
your code seems fail testing “abcdabcde”, what would you think about the code below

String str=”abcdabcde”;
String subStr = “”;
String tmpStr = “”;
for (int i = 0; i subStr.length()) {
subStr = tmpStr;
}
tmpStr = “” + c;
}
}
if (tmpStr.length() > subStr.length()) {
subStr = tmpStr;
}
System.out.println(subStr+”:”+subStr.length());

VA:F [1.9.22_1171]
0
5. jscw

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. João Paulo

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]
-2
7. Jagdish

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. Dinesh

#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. Pushparajan

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
1. anonymous

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
1. Pushparajan

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
1. Pushparajan

sorry, its not O(n).. its O(char_set_size)

VA:F [1.9.22_1171]
0
10. YAO

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]
+1
1. YAO

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
1. dennis

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. Xinhao

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.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. karl

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 = { -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. karl

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;
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
14. Zain

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. maxq

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. Abhishek

here is a java solution to the problem

import java.util.*;
public class longestUniqueSubstring {
public static void main(String args[]){
String input = “abcaadcbacd”;
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. gj477

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;
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. wayne

Abhishek, nice java code, thanks

VA:F [1.9.22_1171]
0
19. Hao Yu

int lengthOfLongestSubstring(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
bool status = { 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. Hao Yu

sorry, paste failed.

int lengthOfLongestSubstring(string s)
{

}

VN:F [1.9.22_1171]
0
21. Hao Yu

int lengthOfLongestSubstring(string s)
{
int i = 0;
int j = 0;
int n = s.length();
int length = 0;
int max = 0;
bool status = { false };
while( i max )
max = length;
}
}
return max;
}

VN:F [1.9.22_1171]
0
22. Siddharth

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
1. Siddharth

My bad its correct 🙂

VA:F [1.9.22_1171]
0
23. Anon

char s[] = “aaaafghaksdljweojlaskdjhiiuaaaaaaaa”;
unsigned char e;
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. gaurav singh panwar

nicely explained..

VN:F [1.9.22_1171]
0
25. Rabbit

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. Subramanian Ganapathy

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
1. Subramanian Ganapathy

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. mrityunjay

int longestSubstr( char str[], int len )
{
int charMap = {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. kuldeep singh Rana

how i can find all the longest substrings but not the length

VA:F [1.9.22_1171]
0
29. roger

VN:F [1.9.22_1171]
0
30. shr-

VN:F [1.9.22_1171]
0
31. Rock

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. ptolemy

VA:F [1.9.22_1171]
0
33. prasad

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
34. Pandoragon

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
35. Payne

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;
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
36. cjhuo

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
1. cjhuo

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; int [] asciiTab = new int; // 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 = i; result = 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-result 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-result < j-i+1){ result = i; result = j+1; } } asciiTab[charArray[j]] = j; // update bookkeeping ```

``` } return (result-result); } }```

VN:F [1.9.22_1171]
0
1. cjhuo

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;
int [] asciiTab = new int; // 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 = i;
result = 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-result 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-result < j-i+1){
result = i;
result = j+1;
}
}

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

}
return (result-result);
}
}

VN:F [1.9.22_1171]
0
1. cjhuo

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
1. cjhuo

last try….

VN:F [1.9.22_1171]
0
37. Kamal Joshi

VN:F [1.9.22_1171]
0
1. Kamal Joshi

Fixed version

VN:F [1.9.22_1171]
0
38. harish chader

<?php
\$rest = substr("abcdef", , );
echo "\$rest”;
?>
without start length and size of length of string in php

VA:F [1.9.22_1171]
0
39. Aephi

superb！

VN:F [1.9.22_1171]
0
40. roota

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
41. glebl

VN:F [1.9.22_1171]
0
42. Mosight

VN:F [1.9.22_1171]
0
43. Mosight

Sorry for previous wrong post with missing part.

VN:F [1.9.22_1171]
0
44. Mosight

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
45. Mao Zhao

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
46. leo wang

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
47. Danfei Xu

int lstr(string str){
int exist;
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
48. ariesxiao

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
49. Sachin

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
50. Sachin

Here is the code for getting all possible longest continuous substrings in Java !:

VN:F [1.9.22_1171]
0
1. Sachin

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
51. dennis

Hi 1377coder,

could you please explain the following code snippet:

VA:F [1.9.22_1171]
0
52. lunci

VN:F [1.9.22_1171]
0
53. feliciafay

That’s a really elegant solution! Thanks a lot!

VN:F [1.9.22_1171]
0
54. siddharthbhide28

char* lengthOfLongestSubstring(char a[])
{
char *p1,*p2;
p1=a;
int i=0;
char static visitarr={NULL};
bool matchfound=false;
visitarr=*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
55. LK

VA:F [1.9.22_1171]
0
1. Derek

You need to update si = Math.max(start, map.get(c[ei]));

VA:F [1.9.22_1171]
0
56. Charaling

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
57. Emettant

how about such compact solution?

VN:F [1.9.22_1171]
0
58. bright

you can make it more efficient by changing the boolean[] to int[]

VN:F [1.9.22_1171]
0
59. kaivalya

Here is a java code. Tested.

VA:F [1.9.22_1171]
0
60. Noob

What is the ans for this case?
“wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco”
ans : 10 ?

VA:F [1.9.22_1171]
0
61. huz

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

VA:F [1.9.22_1171]
0
62. xli141

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
63. xli141

To support my above discussion, here is my code in Java.

VN:F [1.9.22_1171]
0
1. xli141

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
2. xli141

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
64. rong

15-line codes:

VA:F [1.9.22_1171]
+3
65. Pei Wang

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
1. Pei Wang

the missing includes are “iostream”, “set”, “vector” and “sstream”

VA:F [1.9.22_1171]
0
1. Pei Wang

let me try again

VA:F [1.9.22_1171]
0
66. rohit

#include
#include
#include
main()
{
int t;
scanf(“%d”,&t);
while(t–){
char c,ar;int l,i,j,pos=-1,cnt=1,cur=1,max=1,x;
scanf(“%s”,c);fflush(stdin);
ar=c;
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
67. Shivadeep Borgohain

public static int longestNonRepSubstring(String [] str){

int i=0;int j=0; int max1=0;
while(i<str.length){

j=i+1; int count=1;
while(j<str.length){

if(!str[i].equals(str[j])){
count++;

}
else break;
j++;
}

max1= Math.max(count, max1);

i++;
}

return max1;

}

VA:F [1.9.22_1171]
0