Maximum Substring With Non Repeating Characters Solution

You are required to find the longest substring without repeating characters and return the length.

Solution 1: Brute force

The brute force approach generates all substrings and passes them to a function called "unique." This function checks if all characters in the string between the starting and ending index are unique. The function uses a set to verify the uniqueness of the characters present in the substring. The function traverses the string and inserts all characters found into a set. If a character already exists in the set, it returns false.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        answer = 0
        for i in range(0, n):
            for j in range(i + 1, n+1):
                if(self.unique(s, i, j)):
                    answer = max(answer, j - i)
        return answer
    def unique(self, s, start, end):
        charSet = set()
        for i in range(start, end):
            char = s[i]
            if(char in charSet):
                return False
            charSet.add(char)
        return True

Time complexity: O(n³). This is because the solution generates all substrings and checks if they are unique.

Space complexity: O(min(n, m)). Extra space will be used for the set. This set's size is bounded by the length of the string "n" and the characters contained in the set "m".

Solution 2: Sliding Window

The second approach makes use of two pointers. One pointer "i" is used to contract the window while the other pointer "j" is used to expand it. In this approach we make use of a set to check if characters are repeated. We will traverse the string and check if the character at position j is not present in the set. If it is not present, we will add the character to the set, expand the window by incrementing j, and update the maximum length of the window accordingly. Otherwise, if the character is present, we will contract the window by removing the character at position "i" from the set and incrementing i. Note: in the latter scenario, pointer "j" is not incremented; this will allow us check if the character is still present in the set in the next iteration.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        n = len(s)
        answer = 0
        i = 0
        j = 0
        while(i < n and j < n):
            if(not(s[j] in charSet)):
                charSet.add(s[j])
                j+=1
                answer = max(answer, j - i)
            else:
                charSet.remove(s[i])
                i+=1
        return answer

Time complexity: O(2n) = O(n). The string will be traversed twice by i and j in the worst case.

Space complexity: O(min(n, m)). Extra space will be used for the set. This set's size is bounded by the length of the string "n" and the characters contained in the set "m".

Solution 3: Sliding Window Optimised

The third approach is an optimised version of the second. In the second approach, whenever we find a character that is repeated, we contract the window by moving pointer "i" one step ahead. However, the character at position "j" might still have a repeating character in the set which has not been reached yet by pointer "i". We will need to continue contracting the window one step at a time until we find the character that is repeated. This can be costly. We can optimise the algorithm by keeping track of each character's last index with the help of a map. That way, when a character is repeated, we can simply navigate to the index of the repeated character and begin our window from there. Whenever we find a character that is present in the map, we will compare the pointer "i" to the index in the map and update i based on which is greater.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        map = {}
        n = len(s)
        answer = 0
        i = 0
        j = 0
        while(j < n):
            if(s[j] in map):
                i=max(map[s[j]], i)
            answer = max(answer, j - i + 1)
            map[s[j]] = j+1
            j+=1
        return answer

Time complexity: O(n). The string will be traversed once by j.

Space complexity: O(min(m, n)). Extra space will be used for the set. This set's size is bounded by the length of the string "n" and the characters contained in the set "m".