Find the length of the longest no-repeated substring e.g. string without repeating characters. For example, the longest substring without repeating letters

ExampleString s="abcabcbbba" Answer will be "abc" of length 3

Algorithm:

Assuming string has small letter only temp array is of length 26.

Take an temp boolean array to set/reset character is present or not

while iterating through whole string using temp array If character value is already set or true then reset values from current index to previous starting index.and update max-length of non-repeated sub-string.e.g.When you have found a repeated character (let’s say at index j), it means that the current sub-string (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 sub-strings that start before or at index i would be less than your current maximum, you can safely start to look for the next sub-string with head which starts exactly at index i+1.

As we are using two indexes which iterates through string two times e.g. O(2m) where m is length of string  and overall time complexity O(m) .

Lets have a look at Code

int lengthOfLongestSubstring(string s) 
{

  int m= s.length();

  int i = 0, j = 0;

  int maxLen = 0;

 boolean temp[]=new boolean[256];

  while (j < m) {

    if (temp[s[j]]) {

      maxLen = max(maxLen, j-i);

      while (s[i] != s[j])
      {

        temp[s[i]] = false;

        i++;

      }

      i++;

      j++;

    } else  
    {

      temp[s[j]] = true;

      j++;

    }

  }

  maxLen = max(maxLen, m-i);

  return maxLen;

}

Time Complexity O(M)  M is Length of String