• 0

Length of Longest Substring Without Repeating Characters

Example

Given "bbb", the answer is 1.

Given "pwwke", the answer is 3.

Given "obamacare", the answer is 4.

Algorithm

Time complexity: O(n)

  1. Have a pointer which tracks the starting index of the current substring
  2. Create a map of each character and its index
    1. If the current character is in the lookup
      1. Change the starting index
  3. Add the current character to the map
  4. Update the max length of the substring

Notes: Naive solution for this problem takes O ( n^2 ) time which is provided below for reference. The way we make the naive algorithm more time efficient is by realizing one simple observation.

Let's say we are tracking the length of one substring. While looping over the original string at index 5, we find a character which exists in the current substring let's say character "A" at index 3.

If the substring with the longer length exist then it must start from index 4.  Hence, the equation for start in the below solution.


Solution


The naive solution is to iterate over the string and for each character create substring until you find the repeating character.

Time complexity: O (n^2)

Naive Solution