Find longest substring without repeating characters

Question

Given a string S of length N find longest substring without repeating characters.

Example:

Input: "stackoverflow"

Output: "stackoverfl"

If there are two such candidates, return first from left. I need linear time and constant space algorithm.

Answer 1

package com.example.demo;

import java.util.*;

public class LongestSubstring {
    List<Character> k = new ArrayList<Character>();
    List<Character> b = new ArrayList<Character>();

    public void method(char[] x){
        for(int i=0;i<x.length;i++) {
            if (b.contains(x[i])) {
                if (b.size() > k.size()) {
                    k.clear();k.addAll(b);
                }
                b.clear();
                b.add(x[i]);
            } else {
                b.add(x[i]);
            }
        }
    
        System.out.println(k);
    }

    public static void main(String[] args) {
        String input = "abccdbavecddea";
        char[] x = input.toCharArray();

        LongestSubstring o= new LongestSubstring();

        o.method(x);
    }
}

Answer 2

EDITED:

following is an implementation of the concesus. It occured to me after my original publication. so as not to delete original, it is presented following:

public static String longestUniqueString(String S) {
    int start = 0, end = 0, length = 0;
    boolean bits[] = new boolean[256];
    int x = 0, y = 0;
    for (; x < S.length() && y < S.length() && length < S.length() - x; x++) {
        bits[S.charAt(x)] = true;
        for (y++; y < S.length() && !bits[S.charAt(y)]; y++) {
            bits[S.charAt(y)] = true;
        }
        if (length < y - x) {
            start = x;
            end = y;
            length = y - x;
        }
        while(y<S.length() && x<y && S.charAt(x) != S.charAt(y))
            bits[S.charAt(x++)]=false;
    }
    return S.substring(start, end);
}//

ORIGINAL POST:

Here is my two cents. Test strings included. boolean bits[] = new boolean[256] may be larger to encompass some larger charset.

public static String longestUniqueString(String S) {
    int start=0, end=0, length=0;
    boolean bits[] = new boolean[256];
    int x=0, y=0;
    for(;x<S.length() && y<S.length() && length < S.length()-x;x++) {
        Arrays.fill(bits, false);
        bits[S.charAt(x)]=true;
        for(y=x+1;y<S.length() && !bits[S.charAt(y)];y++) {
            bits[S.charAt(y)]=true;
        }           
        if(length<y-x) {
            start=x;
            end=y;
            length=y-x;
        }
    }
    return S.substring(start,end);
}//

public static void main(String... args) {
    String input[][] = { { "" }, { "a" }, { "ab" }, { "aab" }, { "abb" },
            { "aabc" }, { "abbc" }, { "aabbccdefgbc" },
            { "abcdeafghicabcdefghijklmnop" },
            { "abcdeafghicabcdefghijklmnopqrabcdx" },
            { "zxxaabcdeafghicabcdefghijklmnopqrabcdx" },
            {"aaabcdefgaaa"}};
    for (String[] a : input) {
        System.out.format("%s  *** GIVES ***  {%s}%n", Arrays.toString(a),
                longestUniqueString(a[0]));
    }
}

Answer 3

You keep an array indicating the position at which a certain character occurred last. For convenience all characters occurred at position -1. You iterate on the string keeping a window, if a character is repeated in that window, you chop off the prefix that ends with the first occurrence of this character. Throughout, you maintain the longest length. Here's a python implementation:

def longest_unique_substr(S):
  # This should be replaced by an array (size = alphabet size).
  last_occurrence = {} 
  longest_len_so_far = 0
  longest_pos_so_far = 0
  curr_starting_pos = 0
  curr_length = 0

  for k, c in enumerate(S):
    l = last_occurrence.get(c, -1)
    # If no repetition within window, no problems.
    if l < curr_starting_pos: 
        curr_length += 1
    else:
        # Check if it is the longest so far
        if curr_length > longest_len_so_far: 
            longest_pos_so_far = curr_starting_pos
            longest_len_so_far = curr_length
        # Cut the prefix that has repetition
        curr_length -= l - curr_starting_pos
        curr_starting_pos = l + 1
    # In any case, update last_occurrence
    last_occurrence[c] = k

  # Maybe the longest substring is a suffix
  if curr_length > longest_len_so_far:
    longest_pos_so_far = curr_starting_pos
    longest_len_so_far = curr_length

  return S[longest_pos_so_far:longest_pos_so_far + longest_len_so_far]

Answer 4

O(n) solution with few lines of python code

def longestSub(word):

  longest = word[0]
  length = 1
  for i in range(0, len(word)-1):
    current = word[i]
    next = word[i+1]
   # print(current,next)
    if(next not in longest):
      longest += next
      print(longest)
    else:
      longest = longest.replace(longest, "") + next
      print(longest)

    length = length if length > len(longest) else len(longest)

  print(length)

Answer 5

Leetcode accepted answer Longest substring without repeating character

var lengthOfLongestSubstring = function (s) {
    let str = '', count = 0, conatinSC = containsSpecialChars(s);
    for (let i = 0; i < s.length; i++) {
        if (s[i] != ' ') {
            if (str && ((conatinSC && str.match(/s[i]/) || (!conatinSC && str.match(s[i]))))) {
                if (count < str.length) {
                    count = str.length;
                }
                if (str[i - 1] == s[i]) {
                    str = s[i];
                } else {
                    str = str.substring(containsSpecialChars(s[i]) ? str.match(/s[i]/).index + 1 : str.match(s[i]).index + 1) + s[i];
                }

            } else {
                str += s[i];
                if (count < str.length) {
                    count = str.length;
                }
            }
        } else {
            count++;
            break;
        }

    }
    return count;
};
function containsSpecialChars(str) {
    const specialChars = /[`@#$%^&*()_+\-=\[\]{};':"\\|,.<>\/?~]/;
    return specialChars.test(str);
}
lengthOfLongestSubstring("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abc");

Answer 6

^{I was asked the same question in an interview.}

I have written Python3 code, to find the first occurrence of the substring with all distinct chars. In my implementations, I start with index = 0 and iterate over the input string. While iterating used a Python dict seems to store indexes of chars in input-string those has been visited in the iteration.

In iteration, if char c, does not find in current substring – raise KeyError exception

if c is found to be a duplicate char in the current substring (as c previously appeared during iteration – named that index last_seen) start a new substring

def lds(string: str) -> str:
    """ returns first longest distinct substring in input `string` """
    seens = {}
    start, end, curt_start = 0, 0, 0
    for curt_end, c in enumerate(string):
        try:
            last_seen = seens[c]
            if last_seen < curt_start:
                raise KeyError(f"{c!r} not found in {string[curt_start: curt_end]!r}")
            if end - start <  curt_end - curt_start:
                start, end = curt_start, curt_end
            curt_start = last_seen + 1
        except KeyError:
            pass
        seens[c] = curt_end
    else: 
        # case when the longest substring is suffix of the string, here curt_end
        # do not point to a repeating char hance included in the substring
        if string and end - start <  curt_end - curt_start + 1:
            start, end = curt_start, curt_end + 1
    return string[start: end]

Answer 7

C# Solution for defining length of the longest substring without repeating characters:

public int LengthOfLongestSubstring(string s) {
        if (string.IsNullOrEmpty(s))
                return 0;
        if (s.Length==1)
                return 1;
        var l = 0;
            for (int i = 0; i < s.Length - 1; i++)
            {
                var tmp = "" + s[i];
                for (int j = i + 1; j < s.Length; j++)
                    if (tmp.Contains(s[j].ToString())) break;
                    else tmp += s[j];
                if (l < tmp.Length)
                    l = tmp.Length;
            }
            return l;
    }

Answer 8

A simplified solution in javascript.

function longestUniqueString(s) {    
      let i = 0;
      let j = 0;
      let max = 0;
      let set = {};
      let longestString = "";
        
      while(i < s.length - max){
        if(!set[s[j]]){
          set[s[j]] = s[j]; 
          j++;
          max = Math.max(max, j-i);
          if(max <= j-i) longestString = Object.keys(set).join(""); 
        }else{
          i++;
          j = i;
          set = {};
        }
      }
      
      return longestString;
}

// I/O for snippet
console.log(longestUniqueString("stackoverflow"));

Answer 9

Easy python code:

value = 0 
substring = ""

for i in s:
  if i not in substring:
    substring += i
    value = max(value, len(substring))
  else:
    cut_index = substring.index(i)
    substring = substring[cut_index+1:] + i

return value

Answer 10

static int longestsub(String str) {
    int res = 0;
    int start = -1;
    HashMap<Character,Integer> hm = new HashMap<>();
    for(int i = 0; i < str.length(); i++){
        char c = str.charAt(i);
        start = Math.max(start,hm.getOrDefault(c, start));
        res = Math.max(i -  start ,maxLen);
        hm.put(c,i); // update the index
    }
    return res;
}

Answer 11

i’ve also solved this problem, below my 2 solutions written in JavaScript (Brute Force and Sliding Window) + YouTube video with explanation https://youtu.be/1NzWlRP3yfI

/**
 * @param {string} s
 * @return {number}
 */

// //BRUTE FORCE
// var lengthOfLongestSubstring = function(s) {

//     let count = 0;

//     for (let i = 0; i < s.length; i++) {
//         let char = s.charAt(i);
//         let set = new Set([char]);

//         for (let j = i+1; j < s.length; j++) {
//             let char = s.charAt(j);
//             if (set.has(char)) {
//                 break;
//             } else {
//                 set.add(char);
//             }
//         }

//         if (set.size > count) {
//             count = set.size;
//         }

//     }

//     return count;
// };

//SLIDING WINDOW
var lengthOfLongestSubstring = function(s) {

    let count = 0;
    let i = 0;
    let j = 0;
    let n = s.length;
    let set = new Set();

    while (i < n && j < n) {
        let char = s.charAt(j);
        if(!set.has(char)) {
            set.add(char);
            j++;
            count = Math.max(count, j - i)
        } else {
            set.delete(s.charAt(i));
            i++;
        }
    }

    return count;
};

Answer 12

Longest substring without repeating character in python

public int lengthOfLongestSubstring(String s) {
    if(s.equals(""))
        return 0;
    String[] arr = s.split("");
    HashMap<String,Integer> map = new HashMap<>();
    Queue<String> q = new LinkedList<>();

    int l_till = 1;
    int l_all = 1;
    map.put(arr[0],0);
    q.add(arr[0]);
    for(int i = 1; i < s.length(); i++){
        if (map.containsKey(arr[i])) {
            if(l_till > l_all){
                l_all = l_till;
            }
            while(!q.isEmpty() && !q.peek().equals(arr[i])){
                map.remove(q.remove());
            }
            if(!q.isEmpty())
               map.remove(q.remove());
            q.add(arr[i]);
            map.put(arr[i],i);
            //System.out.println(q);
            //System.out.println(map);
            l_till = q.size();
        }
        else {
            l_till = l_till + 1;
            map.put(arr[i],i);
            q.add(arr[i]);
        }
    }
    if(l_till > l_all){
                l_all = l_till;
            }
    return l_all;
}

Answer 13

Tested and working. For easy understanding, I suppose there's a drawer to put the letters.

Function:

    public int lengthOfLongestSubstring(String s) {
        int maxlen = 0;
        int start = 0;
        int end = 0;
        HashSet<Character> drawer = new HashSet<Character>(); 
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (drawer.contains(ch)) {
                //search for ch between start and end
                while (s.charAt(start)!=ch) {
                    //drop letter from drawer
                    drawer.remove(s.charAt(start));
                    start++;
                }
                //Do not remove from drawer actual char (it's the new recently found)
                start++;
                end++;
            }
            else {
                drawer.add(ch);
                end++;
                int _maxlen = end-start;
                if (_maxlen>maxlen) {
                    maxlen=_maxlen;
                }
            }
        }
        return maxlen;
    }

Answer 14

I have implemented similar kind of solution in Java. I am returning the length of string instead of whole string.

Find below solution for the refernece:

public int getLengthOfLongestSubstring(String input) {
        char[] chars = input.toCharArray();
        String longestString = "";
        String oldString="";
        for(int i= 0; i < chars.length;i++) {
            if (longestString.contains(String.valueOf(chars[i])))
            {
                if(longestString.length() > oldString.length()){
                    oldString = longestString;
                }
                if(longestString.split(String.valueOf(chars[i])).length>1)
                    longestString= longestString.split(String.valueOf(chars[i]))[1]+(chars[i]);
                else{
                    longestString =String.valueOf(chars[i]);
                }
            }
            else{
                longestString =longestString+chars[i];
            }
        }
        return  oldString.length()< longestString.length()? longestString.length(): oldString.length();
    }

Or can use following link as a reference.

Git URL

Answer 15

public int lengthOfLongestSubstring(String s) {
    int startIndex = 0;
    int maxLength = 0;
    //since we have 256 ascii chars
    int[] lst = new int[256];
    Arrays.fill(lst,-1);
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        //to get ascii value of c
        int ic = (int) c;
        int value = lst[ic];
        //this will say to move start index to next index of the repeating char
        //we only do this if the repeating char index is greater than start index
        if (value >= startIndex) {
            maxLength = Math.max(maxLength, i - startIndex);
            startIndex = value + 1;
        }
        lst[ic] = i;
    }
    //when we came to an end of string
    return Math.max(maxLength,s.length()-startIndex);
}

This is the fastest and it is linear time and constant space

Answer 16

The solution in C.

#include<stdio.h>
#include <string.h>

void longstr(char* a, int *start, int *last)
{
    *start = *last = 0;
    int visited[256];
    for (int i = 0; i < 256; i++)
    {
        visited[i] = -1;
    }
    int max_len = 0;
    int cur_len = 0;
    int prev_index;
    visited[a[0]] = 0;
    for (int i = 1; i < strlen(a); i++)
    {
        prev_index = visited[a[i]];
        if (prev_index == -1 || i - cur_len > prev_index)
        {
            cur_len++;
            *last = i;
        }
        else
        {
            if (max_len < cur_len)
            {
                *start = *last - cur_len;
                max_len = cur_len;
            }
            cur_len = i - prev_index;
        }
        visited[a[i]] = i;
    }
    if (max_len < cur_len)
    {
        *start = *last - cur_len;
        max_len = cur_len;
    }
}

int main()
{
    char str[] = "ABDEFGABEF";
    printf("The input string is %s \n", str);
    int start, last;
    longstr(str, &start, &last);
    //printf("\n %d  %d \n", start, last);
    memmove(str, (str + start), last - start);
    str[last] = '\0';
    printf("the longest non-repeating character substring is %s", str);
    return 0;
}

Answer 17

Algorithm:
1) Initialise an empty dictionary dct to check if any character already exists in the string.
2) cnt - to keep the count of substring without repeating characters.
3)l and r are the two pointers initialised to first index of the string.
4)loop through each char of the string.
5) If the character not present in the dct add itand increse the cnt.
6)If its already present then check if cnt is greater then resStrLen.
7)Remove the char from dct and shift the left pointer by 1 and decrease the count.
8)Repeat 5,6,7 till l,r greater or equal to length of the input string.
9)Have one more check at the end to handle cases like input string with non-repeating characters.

Here is the simple python program to Find longest substring without repeating characters

a="stackoverflow"
strLength = len(a)
dct={}
resStrLen=0
cnt=0
l=0
r=0
strb=l
stre=l
while(l<strLength and r<strLength):
    if a[l] in dct:
        if cnt>resStrLen:
            resStrLen=cnt
            strb=r
            stre=l
        dct.pop(a[r])
        cnt=cnt-1
        r+=1    
    else:
        cnt+=1
        dct[a[l]]=1
        l+=1

if cnt>resStrLen:
    resStrLen=cnt
    strb=r
    stre=l

print "Result String Length : "+str(resStrLen)
print "Result String : " + a[strb:stre]

Answer 18

can we use something like this .

def longestpalindrome(str1):
    arr1=list(str1)
    s=set(arr1)
    arr2=list(s)
    return len(arr2)



str1='abadef'
a=longestpalindrome(str1)
print(a)

if only length of the substring is to be returned

Answer 19

1. You are going to need a start and an end locator(/pointer) for the string and an array where you store information for each character: did it occour at least once?

2. Start at the beginning of the string, both locators point to the start of the string.

3. Move the end locator to the right till you find a repetition (or reach the end of the string). For each processed character, store it in the array. When stopped store the position if this is the largest substring. Also remember the repeated character.

4. Now do the same thing with the start locator, when processing each character, remove its flags from the array. Move the locator till you find the earlier occurrence of the repeated character.

5. Go back to step 3 if you haven't reached the end of string.

Overall: O(N)

Answer 20

def max_substring(string):
   last_substring = ''
   max_substring  = ''
   for x in string:
       k = find_index(x,last_substring)
       last_substring = last_substring[(k+1):]+x
       if len(last_substring) > len(max_substring):
               max_substring  = last_substring        
   return max_substring

def find_index(x, lst):
   k = 0
   while k <len(lst):
      if lst[k] == x:
         return k
      k +=1
   return -1

Answer 21

Question: Find the longest substring without repeating characters. Example 1 :

    import java.util.LinkedHashMap;
    import java.util.Map;

    public class example1 {

        public static void main(String[] args) {
            String a = "abcabcbb";
               // output => 3
            System.out.println( lengthOfLongestSubstring(a));

        }

        private static int lengthOfLongestSubstring(String a) {
               if(a == null  || a.length() == 0) {return  0 ;}  
               int res = 0 ;
            Map<Character , Integer> map = new LinkedHashMap<>();
              for (int i = 0; i < a.length(); i++) {
                  char ch = a.charAt(i);
                if (!map.containsKey(ch)) {
       //If ch is not present in map, adding ch into map along with its position
                    map.put(ch, i);

                }else {
/*
If char ch is present in Map, reposition the cursor i to the position of ch and clear the Map.
*/ 
                    i = map.put(ch, i);// updation of index
                     map.clear();
                }//else

                res = Math.max(res, map.size());

            }



            return res;
        }

    }

if you want the longest string without the repeating characters as output then do this inside the for loop:

String res ="";// global
    int len = 0 ;//global
 if(len < map.size()) {
     len = map.size();
    res = map.keySet().toString();
 }
System.out.println("len -> " + len);
System.out.println("res => " + res);

Answer 22

This problem can be solved in O(n) time complexity. Initialize three variables

1. Start (index pointing to the start of the non repeating substring, Initialize it as 0 ).
2. End (index pointing to the end of the non repeating substring, Initialize it as 0 )
3. Hasmap (Object containing the last visited index positions of characters. Ex : {'a':0, 'b':1} for string "ab")

Steps : Iterate over the string and perform following actions.

1. If the current character is not present in hashmap (), add it as to hashmap, character as key and its index as value.

2. If current character is present in hashmap, then

   a) Check whether the start index is less than or equal to the value present in the hashmap against the character (last index of same character earlier visited),

   b) it is less then assign start variables value as the hashmaps' value + 1 (last index of same character earlier visited + 1);

   c) Update hashmap by overriding the hashmap's current character's value as current index of character.

   d) Calculate the end-start as the longest substring value and update if it's greater than earlier longest non-repeating substring.

Following is the Javascript Solution for this problem.

var lengthOfLongestSubstring = function(s) {
    let length = s.length;
    let ans = 0;
    let start = 0,
        end = 0;
    let hashMap = {};

    for (var i = 0; i < length; i++) {

        if (!hashMap.hasOwnProperty(s[i])) {
            hashMap[s[i]] = i;
        } else {
            if (start <= hashMap[s[i]]) {
                start = hashMap[s[i]] + 1;
            }
            hashMap[s[i]] = i;
        }
        end++;
        ans = ans > (end - start) ? ans : (end - start);
    }
    return ans;
};

Answer 23

Here are two ways to approach this problem in JavaScript.

A Brute Force approach is to loop through the string twice, checking every substring against every other substring and finding the maximum length where the substring is unique. We'll need two functions: one to check if a substring is unique and a second function to perform our double loop.

// O(n) time
const allUnique = str => {
  const set = [...new Set(str)];
  return (set.length == str.length) ? true: false;
}

// O(n^3) time, O(k) size where k is the size of the set
const lengthOfLongestSubstring = str => {
  let result = 0,
      maxResult = 0;
  for (let i=0; i<str.length-1; i++) {
    for (let j=i+1; j<str.length; j++) {
      if (allUnique(str.substring(i, j))) {
        result = str.substring(i, j).length;
        if (result > maxResult) {
          maxResult = result;
        }
      }
    }
  return maxResult;
  }
}

This has a time complexity of O(n^3) since we perform a double loop O(n^2) and then another loop on top of that O(n) for our unique function. The space is the size of our set which can be generalized to O(n) or more accurately O(k) where k is the size of the set.

A Greedy Approach is to loop through only once and keep track of the maximum unique substring length as we go. We can use either an array or a hash map, but I think the new .includes() array method is cool, so let's use that.

const lengthOfLongestSubstring = str => {
  let result = [],
      maxResult = 0;

  for (let i=0; i<str.length; i++) {
    if (!result.includes(str[i])) {
      result.push(str[i]);
    } else {
      maxResult = i;
    }
  }

  return maxResult;
}

This has a time complexity of O(n) and a space complexity of O(1).

Answer 24

simple python snippet l=length p=position maxl=maxlength maxp=maxposition

Answer 25

import java.util.HashMap;
import java.util.HashSet;

public class SubString {
    public static String subString(String input) {

        String longesTillNOw = "";

        String longestOverAll = "";
        HashMap<Character,Integer> chars = new HashMap<>();
        char[] array=input.toCharArray();
        int start=0;
        for (int i = 0; i < array.length; i++) {
            char charactor = array[i];
            if (chars.containsKey(charactor) ) {
                start=chars.get(charactor)+1;
                i=start;
                chars.clear();
                longesTillNOw = "";
            } else {
                chars.put(charactor,i);
                longesTillNOw = longesTillNOw + charactor;
                if (longesTillNOw.length() > longestOverAll.length()) {
                    longestOverAll = longesTillNOw;
                }
            }
        }
        return longestOverAll;

    }

    public static void main(String[] args) {
        String input = "stackoverflowabcdefghijklmn";
        System.out.println(subString(input));
    }
}

Answer 26

I modified my solution to "find the length of the longest substring without repeating characters".

        public string LengthOfLongestSubstring(string s) {
    var res = 0;
    var dict = new Dictionary<char, int>();
    var start = 0;

    for(int i =0; i< s.Length; i++)
    {
        if(dict.ContainsKey(s[i]))
        {
            start = Math.Max(start, dict[s[i]] + 1); //update start index
            dict[s[i]] = i;
        }
        else
        {
            dict.Add(s[i], i);
        }

        res = Math.Max(res, i - start + 1);  //track max length
    }
    return s.Substring(start,res);
}

Answer 27

here is my javascript and cpp implementations with great details: https://algorithm.pingzhang.io/String/longest_substring_without_repeating_characters.html

We want to find the longest substring without repeating characters. The first thing comes to my mind is that we need a hash table to store every character in a substring so that when a new character comes in, we can easily know whether this character is already in the substring or not. I call it as valueIdxHash. Then, a substring has a startIdx and endIdx. So we need a variable to keep track of the starting index of a substring and I call it as startIdx. Let's assume we are at index i and we already have a substring (startIdx, i - 1). Now, we want to check whether this substring can keep growing or not.

If the valueIdxHash contains str[i], it means it is a repeated character. But we still need to check whether this repeated character is in the substring (startIdx, i - 1). So we need to retrieve the index of str[i] that is appeared last time and then compare this index with startIdx.

• If startIdx is larger, it means the last appeared str[i] is outside of the substring. Thus the subtring can keep growing.
• If startIdx is smaller, it means the last appeared str[i] is within of the substring. Thus, the substring cannot grow any more. startIdx will be updated as valueIdxHash[str[i]] + 1 and the new substring (valueIdxHash[str[i]] + 1, i) has potential to keep growing.

If the valueIdxHash does not contain str[i], the substring can keep growing.

Answer 28

This is my solution. Hope it helps.

  function longestSubstringWithoutDuplication(str) {
      var max = 0;

      //if empty string
      if (str.length === 0){
        return 0;
      } else if (str.length === 1){ //case if the string's length is 1
        return 1;
      }

      //loop over all the chars in the strings
      var currentChar,
          map = {},
          counter = 0; //count the number of char in each substring without duplications
      for (var i=0; i< str.length ; i++){
        currentChar = str.charAt(i);

        //if the current char is not in the map
        if (map[currentChar]  == undefined){
          //push the currentChar to the map
              map[currentChar] = i;
              if (Object.keys(map).length > max){
                 max = Object.keys(map).length;
              }
        } else { //there is duplacation
          //update the max
          if (Object.keys(map).length > max){
            max = Object.keys(map).length;
          }
          counter = 0; //initilize the counter to count next substring
          i = map[currentChar]; //start from the duplicated char
          map = {}; // clean the map
        }
      }


     return max;
    }

Answer 29

Another O(n) JavaScript solution. It does not alter strings during the looping; it just keeps track of the offset and length of the longest sub string so far:

function longest(str) {
    var hash = {}, start, end, bestStart, best;
    start = end = bestStart = best = 0;
    while (end < str.length) {
        while (hash[str[end]]) hash[str[start++]] = 0;
        hash[str[end]] = 1;
        if (++end - start > best) bestStart = start, best = end - start;
    }
    return str.substr(bestStart, best);
}
 
// I/O for snippet
document.querySelector('input').addEventListener('input', function () {
    document.querySelector('span').textContent = longest(this.value);
});

Enter word:<input><br>
Longest: <span></span>

Answer 30

Not quite optimized but simple answer in Python

def lengthOfLongestSubstring(s):
      temp,maxlen,newstart = {},0,0
      for i,x in enumerate(s):
            if x in temp:
                  newstart = max(newstart,s[:i].rfind(x)+1)
            else:
                  temp[x] = 1
            maxlen = max(maxlen, len(s[newstart:i + 1]))
      return maxlen

I think the costly affair is rfind which is why it's not quite optimized.