Longest Substring Without Repeating Characters

In the brute force approach, we will use two nested loops. The outer loop is used to select the starting index of the substring and the inner loop is used to fix the ending index of the substring. After selecting the substring, we will use another loop (or a method) to check whether the substring contains all unique characters or not using a HashSet.

In this approach, we will use two nested loops. The outer loop is used to select the starting index of the substring and the inner loop is used to fix the ending index of the substring.

Inside the outer loop, we will initialize a HashSet to store the unique characters. Now we will keep adding the characters to this set using the inner loop. Before adding each character if the character is already present in the set this means that from ith index to current jth index this character is repeated. So we will not consider this substring and any other substring starting from the ith index and ending at j or after, break from the inner loop. Otherwise, we will update the longest length and add the character to the set.

In this approach, we will use a binary search to select the length of the substring. The smallest value possible will be 1 as all the characters are unique substrings themselves and the maximum value for binary search will be ‘L’ as there is no substring wth length more than L in the given string where L is the length of the given input string.

Now doing the binary search on the range start = 1 to end = L. We will check for ‘mid’(start + end)/2 length, whether there is any substring with length equals to ‘mid’ with unique characters or not. If such substring exists we will update the answer and move to right side ie start = mid + 1. Otherwise, we will check on the left side i.e end = mid - 1.

Now to check whether a substring of length ‘mid’ exists on or not we will iterate on the whole string. Given below is the algorithm to check this.

Steps Required to calculate the length:

Boolean isDistinctSubstringExists(input, mid):

1. Initialize the map to store frequencies.
2. For each character in the input, i.e i = 0 to L - 1, where L is the length of the input string.
   • Increment the current character’s frequency in the map.
   • If i >= mid, decrease the frequency of (i - mid)th character. If it is zero remove it from the map.
   • If the map current size equals to the mid-value, return true.
3. No substring of length equals to mid found, return false.

We will keep a window that will keep a range of unique characters where the range is defined by start and end indices. Initially, both ‘start' and ‘end’ equal to zero denoting that we have only one character in the current window i.e the character at 0th index. Along with this, we will also keep a HashMap/ Unordered Map to store the last occurrence of the characters. Now we will keep incrementing the ‘end’ to iterate on each character of the string. 

If the current character at the ‘end’ index is not present in the window we will simply update the ‘start' to the maximum index possible index of ‘start’ or the last occurrence of the current character. Then we update the ‘maxLen’ and it gets updated if the range ('end' - ‘start’ - 1) is greater than ‘maxLen’. Then store the current index in the Map/HashMap as the current index will be the last occurrence of the character till current index iterated. Also, increment the ‘end’ by 1. Finally, Return ‘maxLen’.