How to solve the unique substring problem

Overview

We have to find the longest substring with no repeating character.

What is a substring?

A substring of a string, s, is any contiguous part of the string.

In other words, a substring of the string s is obtained by deleting zero or several characters from the start and/or the end of s.

Here are some valid substrings for s = "Hello World":

• "e"
• "Hello"
• "ello Wor"
• " Worl"
• "o World"
• "Hello World"

Here are some strings that can’t be referred to as a substring of s.

• "H World".
• "Helo Word"
• "HelloWorld"

Example

For s = "armaandutt", the longest substring in s, with no repeating characters, is “andut” with five characters.

For s = "educative", the answer could be either of the following with eight characters each:

• "ducative"
• "educativ"

For s = "edpresso", the answer will be "dpres" with five characters.

The brute force solution

We could simply check for a favorable substring over all substrings of given the string, s. This is the brute force solution. From all these favorable substrings, we can print the longest one.

We have to loop over every (i,j) combination such that i<j and i in the range (0,N) and j in range (i+1,N). This will generate all the substrings of s. This process will take the O(N^2) time complexity.

To check if a substring is favorable or not, we’ll have to make another loop from [i-j]. By doing this, we check if there are any repeating characters. Therefore, the final time-complexity of the brute force solution will be O(N^3).

The sliding window solution

In the sliding window technique, we create a window (a substring) and keep sliding it from start to end. We do this by expanding from the right and contracting from the left for specific criteria.

Algorithm

• i,j will be the left and right end of our current window. We initialize both of them with 0.

• For every j, idx[x] will be the last occurrence of x before j.

• The longest substring with no repeated characters until the jth index is ans = " ".

• The length of ans until the jth index is maxLen = 0.

We’ll run a while loop for j<n. We’ll increment j by 1 in every iteration.

If s[j] is not present in the current window, we expand the window and add s[j] to it.

If s[j] is present in the current window, we contract the window and replace i by last occurrence of s[j] + 1. This will make it i = idx[ s[ j ] ] + 1.

Moreover, when we extract the window, we add s[j] to the current window.

The time complexity of this approach is O(n).

Explanation

• Line 1: We take the s string as the input.

• Lines 2–7: We initialize the variables as explained in the approach.

• Line 9: We start the while loop until j<n.

• Line 10: We check if s[j] is present in the current window.

• Line 12: If it’s present, we contract the window first and get i = idx[s[j]]+1.

• Line 14: expanding-window i.e., adding s[j] in current window and updating idx, idx[s[j]]=j.

• Line 15: If s[j] is not present in the current window then the statement(s) in else will execute.

• Line 17: We expand the window by adding s[j] in the current window and updating idx to idx[s[j]]=j.

• Line 19: Here, currentLen is the size of the current window, which is j-i+1.

• Line 20: We check if the current window is longer than maxLen.

• Lines 21–22: If the current window is longer than maxLen, we update ans and maxLen.

• Line 23: We increment j.

• Line 24: We print ans.