Length of 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.

Solution:
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).

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

Time Complexity : O(N)

0 Thoughts on “Length of Longest substring without repeating characters

  1. Anonymous on September 15, 2013 at 4:47 pm said:

    Admin you guys are already doing a great job.It would be much more useful if you can provide a short description of the logic also.

  2. it will fail for “abcdeafghij”->longest substring would be bcdeafghij

  3. Below is the solution

    public static int LongestNonRepeatedChars(string str)
    {
    if (string.IsNullOrEmpty(str))
    return 0;
    if (str.Length == 1)
    return 1;

    Dictionary dictionaryStr = new Dictionary();
    int maximum = 1;
    int potentialMax = 1;
    dictionaryStr.Add(str[0], str[0]);
    for (int i = 1; i maximum)
    {
    maximum = potentialMax;
    potentialMax = 1;
    }
    dictionaryStr.Clear();
    }
    dictionaryStr.Add(str[i], str[i]);
    }
    if (potentialMax > maximum)
    maximum = potentialMax;
    return maximum;
    }

  4. Shrikant on January 4, 2015 at 2:35 am said:

    Here is the solution:
    public void longestSubString(String str){

    int count=0;
    int maxlen=0;
    int arr[] = new int[256];
    for(int i=0;i<256;i++){
    arr[i]=0;
    }

    int i=0;
    int j=0;

    while(imaxlen){
    maxlen=count;
    }
    count–;
    }
    else{
    arr[str.charAt(i)]=1;
    count++;
    i++;
    }
    }
    if(count>maxlen){
    maxlen=count;
    }

    System.out.println(“Longest Substrin:”+maxlen);
    }

  5. Dima on May 23, 2015 at 3:08 pm said:

    I made in this way (without array of 256 )

    int longest_qnique_substr( char* string )
    {
    int limit = INT_MAX;
    int min_limit = limit;

    char *str = string;
    int offset = 0;
    while( *str && (str – string ) limit) ? limit :min_limit;
    str++;
    offset++;
    }

    return min_limit;
    }

  6. jijo jose on August 12, 2015 at 8:32 am said:

    #include
    #include
    #include
    using namespace std;
    stack s;

    int main()
    {
    string a;
    int b[100]={0};
    getline(cin,a);
    int m=0;
    for(int i=0; i<a.length(); i++)
    {

    if(i==0)
    {
    s.push(a[i]);
    b[m]++;
    }
    else
    {
    if(a[i]==s.top())
    {
    s.push(a[i]);
    m++;

    }

    else
    {
    b[m]++;
    s.push(a[i]);

    }
    }
    }

    int c;
    c=s.size();
    for(int i=0; i<c; i++)
    cout<<b[i]<<"\n";

    }

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation