3. Longest Substring Without Repeating Characters - LeetCode Fastest Solution

Hello Code Recipian! In our previous article we solved the two sum problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 3 problem.

Problem Statement

For a given input string s, return the length of the longest substring in s without repeating characters. s consists of English letters and digits.

Example 1:

Input: s = "abcabcbb" Output: 3

Example 2:

Input: s = "bbbbb" Output: 1

Example 3:

Input: s = "pwwkew" Output: 3

Solution: Longest Substring Without Repeating Characters

Let us try to understand the problem statement first. This is a pretty straightforward problem if you know what a substring is for a given string.

A substring a continuous sequence of characters in a given string. For example, the substrings of string "abcd" are: "a", "ab", "abc", "abcd", "b", "bc", "bcd", "c", "cd" and "d". If the characters are not continuous it is not considered a substring. "bd", "ad", "acd" etc. are not substrings because the characters are not continuous as compared to the original string s.

Note: Substring is different from a subsequence which may not be consecutive in nature.

Now that we know what a substring is, we need to write an algorithm that returns the length of the longest substring in string s. But wait, remember we cannot just return any substring that is longest as clearly mentioned in the problem statement, we are only allowed to consider substrings without repeating characters. "Substring without repeating characters" is nothing but a substring containing all unique characters, there should not be any duplicate characters/letters in the substring.

This problem can be efficiently solved by using the two pointer sliding window technique. We slide the window forward each time we find a duplicate character. In this approach we need to process each character in the given string only once to find out the result.

Algorithm

For a given input string s this algorithm does the following steps:

1. We take two variables start and end to indicate the start and end of the window. The string between the start and end is our current substring. Initially both start and end point to the 0th index (1st character) of the string s, i.e. start = 0 and end = 0. Also create a result variable to store the required result.

2. Next we create a hashmap which helps us to efficiently check if the current substring contains any duplicate characters. Lets name it charIndexMap. Key to this hashmap is the current character and value of this hashmap is the position of the character represented by the hashmap key in the given string s.

3. In each iteration we check if the current character at end index is present in the charIndexMap or not.

4. If the character is not present, add it to the hashmap along with the index.

5. If the character is present in the map already, it means that the current character is a duplicate and we should not be considering the substring with this character while calculating the result. So, take the length of the substring from the start of the window until the previous character. If the current length is greater than the result, update the result. Also since we have found a duplicate character, we need to update the start index. Another important step here is to remove all characters from the previous window from our hashmap (since we have moved our window by updating the start variable). Finally add the current character to our hashmap along with its index.

How do we update the start variable once a duplicate character is found?

Remember along with storing the characters in hashmap, we also store the index of the character in the string as hashmap value. When we get a duplicate character during our iteration what does this value in hashmap mean? It simply means that the current duplicate character was earlier found at this index represented by the hashmap value (first occurrence). Using this info we discard all the characters before the first occurrence of the duplicate including the first occurrence (discard all characters from previous window). So our new start value will be start = map[current character] + 1.

Note: Character literals are represented by uint8 or rune datatype in go.\

Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Simulation

Lets see the working of the above algorithm with an example:

Consider s = "abcabcbb" is the given string. Initially start = 0 and end = 0 and our hashmap is empty as shown in the figure below. Also we initialize result = 0.

Now we check if s[end] = 'a' is present in our hashmap. Obviously 'a' is not present in hashmap, so we add 'a' as hashmap key and 0 as hashmap value indicating 'a' is found at 0th position in string (index based position). Same is shown in figure below:

Next we increment end pointer.

Again check if s[end] = 'b' is present in map. As 'b' is not present we add it to hashmap as shown in diagram below.

Increment the end pointer, s[end] = 'c', and since it is not in map we add it to our hashmap.

Increment end again. Now s[end] = 'a'.

Now s[end]='a' is present in map, which means it is a duplicate character. Since we are looking only for substrings without repeating characters, we cannot consider the current substring "abca" for our result, so our valid substring is only till the previous character, i.e "abc".

Since we have found a duplicate the next step is to update result. result = max(result , length of substring from index 0 to 2) = max(result , length of substring "abc") = max (3,3) = 3.

Also since the current character is a duplicate, we need to update out start pointer. We update start as start = first occurrence of duplicate + 1. We can get the first occurrence of duplicate from our hashmap. So start = map['a'] + 1 = 0+1 = 1.

Next, remove all the characters before our new start index and previous start index from hashmap (in this case our previous start index was 0 and new start index which we calculated a just before this step is 1) since they are no longer in our new window, so we remove 'a' from hashmap.

Add the current character 'a' to map along with its index to hashmap. Now our diagram looks as shown below:

Increment end pointer, s[end] = 'b'.

Again 'b' is present in map. Update result = max(result , length of substring from index 1 to 3) = max(result , length of substring "bca") = max(3,3) = 3.

Delete previous window characters, i.e. delete 'b' from hashmap.

Update start = map['b']+1 = 1 + 1 = 2 and update hashmap, map['b'] = 4 for current character.

Again we increment end pointer, end = 5 which is character 'c' which is a duplicate.

We repeat the steps of calculate result, removing previous window characters from map, updating the start pointer and adding the current character to map.

result = max(result , length of substring from index 2 to 4) = max(result , length of substring "cab") = max(3,3) = 3.

start = map['c'] + 1 = 2+1 = 3.

Remove character 'c':2 from previous window.

Add the current character 'c': 5 to our hashmap. Now our diagram looks as below:

Increment end pointer again, now end = 6, which is character 'b'. 'b' is also present in our map(we found it earlier at 4 index in our string s).

result = max(result , length of substring from index 3 to 5) = max(result , length of substring "abc") = max(3,3) = 3.

start = map['b'] + 1 = 4+1 = 5 and remove all characters before our new start ('c':5, 'a':3 and 'b':4) from our map. Also we update the current character 'b':6 into map.

Finally we increment end again, our new end = 7. Again 'b' is present in hashmap.

result = max(result , length of substring from index 5 to 6) = max(result , length of substring "cb") = max(3,2) = 3 and start = map['b'] + 1 = 6+1 = 7. Add 'b':7 to map.

The end has now reached the end of the string s, so we terminate the loop and return the result.

Note: The order in which elements are stored in the map does not matter.

Code

Language: Go

Complexity Analysis

Time Complexity: O(n)

We check each character in the string only once. Yes we would also have to delete the elements from the hashmap once a duplicate character is found, but this is a constant time operation because at max the map can store only 62 elements in our case before a duplicate is found.

Space Complexity: O(1)

In the worst case we would have to store all n characters of the string s in hashmap, but this is a constant value which at max can go up to O(62) as explained in solution 1.

That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.

If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).

You can explore more such amazing articles from code recipe in our blogs section.

⚡ FREE Premium Access—Only for a Short Time! ⚡ Love coding? Get expert tutorials, pro tips, and exclusive resources—100% FREE! For a limited time, enjoy full access to Code Recipe Membership at no cost. Don’t wait—grab this deal before time runs out! ⏳ Sign up now!

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.