Longest Substring Without Repeating Characters — Day 19(Python)

Photo by Amador Loureiro on Unsplash

Today we will be working on a String problem. This is one of the favorite questions among Amazon interviewers. Let us jump into the question without wasting much time.

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc" with a length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b" with a length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke" with a length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols, and spaces.

A substring of a string is a contiguous group of characters from the original string.
For eg: A = “Hello World”
Some examples of substring for string A is as follows:
“Hello”, “ “, “world”, “e”, “Hello World”.

One way to find an answer is to find all the substrings possible for the given string. Eliminate those substrings with repeating characters. Finding the maximum length among the remaining substring.

class SubstringFinder:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == "":
            return 0
        substrings = []
        max_len = float('-inf')
        for first in range(len(s)):
            for second in range(first, len(s)):
                substrings.append(s[first:second+1])
        for word in substrings:
            if len(word) == len(set(list(word))):
                if max_len <= len(word):
                    max_len = len(word)
        return max_len

Complexity analysis

Time Complexity

We start with the first character in the string, combine with the remaining characters in the string. On completing all the characters in the string, start with the second character in the string. Repeat the procedure for all the characters. Looking at the code, we notice two nested for loops for creating the subarray. Hence time complexity is O(N²) where N the number of characters in the string.

Space Complexity

We are creating a list to store all the created subarray, and the count of subarray grows as the count of characters increases in the string. Hence the space complexity is O(N²), where N the number of characters in the string.

We do not expect the above algorithm to work well if the size of the string increases. How can we find a better solution?

The problem wants us to find the length of the longest substring without any repeating characters from the original string. We will traverse through each character in the original string, check if the character already exists in the substring formed. If a character is present in the substring, we remove characters until the repeating character and create a substring from the index where we do not have repeating characters.

To check if the current character exists in the substring we can maintain a set that holds characters present in the substring.

Let us look into the code snippet.

class SubstringFinder:
    def lengthOfLongestSubstring(self, s: str) -> int:
        substring_set = set()
        substring = []
        max_len = 0
        for i in range(len(s)):
            if s[i] not in substring_set:
                substring_set.add(s[i])
                substring.append(s[i])
            else:
                while(substring[0]!= s[i]):
                    key = substring.pop(0)
                    substring_set.remove(key)
                key = substring.pop(0)
                substring_set.remove(key)
                substring_set.add(s[i])
                substring.append(s[i])
            max_len = max(max_len, len(substring))
        return max_len

Complexity analysis

Time Complexity

We need to traverse through characters in the string one by one. We observe the presence of the while loop inside for loop in our code. Shouldn’t our time complexity be O(N²)? We are appending characters into our subarray string once and removing it from our string if the character is not supposed to be part of our substring once. Hence time complexity is O(2N) which in turn is O(N).

Space Complexity

We are creating a set to hold character that is processed before. In the worst-case scenario, we might have to store all the letters in String, though the size of the set cannot go beyond 26. Hence space complexity is O(N).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.