Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

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
  1. Create a map of each character and its index
    1. If the current character is in the lookup
      1. Change the starting index
  1. Add the current character to the map
  1. 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

 


 

You may also like...

Leave a Reply

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