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.5/5 (82 votes cast)
Longest Substring Without Repeating Characters, 4.5 out of 5 based on 82 ratings

91 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[0] == None or len(r) > len(longest[0]):
    …………longest[0] = ”.join(r)

    ….for c in s:
    ……..# first character
    ……..if len(r) == 0:
    …………h.add(c)
    …………r.append(c)
    ……..# a new character
    ……..elif c not in h:
    …………h.add(c)
    …………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)
    …………h.add(c)

    ……..candidate()

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

    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]
    -2
  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]
    0
    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.
    Then advance q.

    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;
    ht.Add(str[i], 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
  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]
    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[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. 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[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. 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[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
  14. Zain

    What about this solution. Following One seems bit easy

    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. Profile photo of AbhishekAbhishek

    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 = “”;
    LinkedHashMap temp= new LinkedHashMap();
    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[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. Profile photo of Hao YuHao Yu

    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
  19. Profile photo of Hao YuHao Yu

    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
  20. 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
  21. Anon

    char s[] = “aaaafghaksdljweojlaskdjhiiuaaaaaaaa”;
    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
  22. 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
  23. 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
  24. mrityunjay

    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
  25. Profile photo of rogerroger

    VN:F [1.9.22_1171]
    0
  26. Profile photo of shr-shr-

    VN:F [1.9.22_1171]
    0
  27. 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
  28. ptolemy

    VA:F [1.9.22_1171]
    0
  29. 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
  30. Profile photo of PandoragonPandoragon

    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++) {
    set.add(s.charAt(i));
    }
    return set.size();
    }
    }

    VN:F [1.9.22_1171]
    0
  31. Profile photo of PaynePayne

    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.JMenuItem;
    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
  32. Profile photo of cjhuocjhuo

    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. Profile photo of cjhuocjhuo

      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
      1. Profile photo of cjhuocjhuo

        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
          1. Profile photo of cjhuocjhuo

            last try….

            VN:F [1.9.22_1171]
            0
  33. Profile photo of Kamal JoshiKamal Joshi

    VN:F [1.9.22_1171]
    0
    1. Profile photo of Kamal JoshiKamal Joshi

      Fixed version

      VN:F [1.9.22_1171]
      0
  34. 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
  35. Profile photo of rootaroota

    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
  36. Profile photo of gleblglebl

    VN:F [1.9.22_1171]
    0
  37. Profile photo of MosightMosight

    VN:F [1.9.22_1171]
    0
  38. Profile photo of MosightMosight

    Sorry for previous wrong post with missing part.

    VN:F [1.9.22_1171]
    0
  39. Profile photo of Mao ZhaoMao 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{
    hs.add(s.charAt(j));
    j++;
    }
    }
    return Math.max(max, l-i);
    }
    }

    VN:F [1.9.22_1171]
    0
  40. Danfei Xu

    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
  41. Profile photo of SachinSachin

    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
  42. Profile photo of SachinSachin

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

    VN:F [1.9.22_1171]
    0
  43. Profile photo of luncilunci

    VN:F [1.9.22_1171]
    0
  44. Profile photo of siddharthbhide28siddharthbhide28

    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
  45. LK

    VA:F [1.9.22_1171]
    0
  46. 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
  47. Profile photo of EmettantEmettant

    how about such compact solution?

    VN:F [1.9.22_1171]
    0
  48. kaivalya

    Here is a java code. Tested.

    VA:F [1.9.22_1171]
    0
  49. Noob

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

    VA:F [1.9.22_1171]
    0
  50. huz

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

    VA:F [1.9.22_1171]
    0
  51. Profile photo of xli141xli141

    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
  52. Profile photo of xli141xli141

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

    VN:F [1.9.22_1171]
    0
    1. Profile photo of xli141xli141

      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. Profile photo of xli141xli141

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

    15-line codes:

    VA:F [1.9.22_1171]
    +2
  54. 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

        let me try again

        VA:F [1.9.22_1171]
        0
  55. rohit

    #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
  56. Pingback: Longest Substring Without Repeating Characters | juliachenonsoftware

  57. Pingback: Longest Substring Without Repeating Characters « if(game & design) :)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.