How many substrings exist that have no repeating characters? from Ishita Juneja's blog

In this tutorial we are going to discuss the technicalities attached with the concept of longest substring without repeating the characters!

As string is touted as the most crucial coding interview concept, there are high chances you will encounter the questions on this topic. 

From longest palindromic substring to reversing a string, you will come across several string concepts.

In this blog we have discussed the topic of substrings that exist without non-repeating characters.

Read it in detail and strengthen your knowledge!

Counting longest substring without repeating all the characters 

A string str is given to you which consists of all the lowercase alphabets. Your task would be to find all the possible substrings which only consist of distinct characters. 

For example:

The input is Str = gffg

The output in this case is 6. 

From a given string, you will get the possible strings as g, gf,gff, gffg,f, ff, ffg, f, fg and g.

Among all these strings, the highlighted strings will only consist of the distinct characters. 

Analysis 

To find the longest substring without repeating the character,you will get the input as a string which contains the characters that may not be repeated. Your task would be to find the longest substring with distinct characters. 

One feature of a substring is that it contains all the contiguous characters. In the given string, s =requark, the substrings would be edq, red, ar, quar. 

Though, the substring rd and qur are not valid ones as they contain the characters from its source string or which are not contagious. 

There can be several substrings as the output so as to only return the longest among them. 

Sliding window algorithm 

The sliding window algorithm would be quite useful to find substring with distinct characters. From an input, we can gather the information as:

• A data structure is given which will be a linear data structure

• The output would be a substring that is the part of a string 

• There will be a naive solution for checking if you will get the combination of the each character in a string 

The steps to follow in this case are:

• You are given two pointers which would define a start index with the start and an ending index as end in a current window. They will be 0 in the beginning.

• Declare the set of variables to unique characters that you will encounter with 

• Declare the variable called maxlength to keep track of the required length of the longest substring 

• Scan a required string from its left to right as one character at a given time 

• If the characters are not encountered before, they will not be present as a set in the string to get the increment at the end of an index. The maxlength in this case would be as set.size[]with the existing maxlength 

• Though, if there are characters that have been encountered before which are present in a given set, we will increment it as start to remove all characters at the start of an index

• Repeat the steps to move it till the window 

• After a loop terminates, return it maxlength

As you can see, the strings will be scanned only once from left to right, the time complexity in this case would be O[n].

As you will be using the set of data structure for computations, the space complexity in this case would be the O[n] 

Since, the set will only contain unique characters, you will not get the size of characters more than what is required. 

Brute Force Approach 

This is a simple method to check all required substrings from a given string with that of a nested for loop to check if the substrings would have any duplicate characters.

• Create all variables to track longest_len of the substring encountered. 

• Create the required loop in order to traverse all the substring characters. Then create variables to keep the track of all substrings encountered 

• Create some other loop in order to traverse the characters of a substring. Compare the string length by using the max()function and assign the greater value 

• Use if nested statement to check the length of a previous string with the length of a current string with the lonest_str variable.

• Print the longest substring with its length 

Considering in this case, the string as only substring, the runtime will be O [n ^ 2] the space complexity in the best or worst case would be o [1] 

Using Hashmap 

It takes less time in the dictionary type. Firstly, create a required empty dictionary for tracking all the characters as a key with their respective indexes as a kind of dictionary value. 

Keep the longest substring length in mind with the start of an index for each substring in the loop to determine the length at the end of a loop. 

• First create the empty dictionary with longest_len to keep the track of variables. Then keep the track of the starting indexes with the longest_str

• Create the required for loop for all string characters. Create the if statement to check if it is in the dictionary or not. Check if it has the value greater than that of start variable or the value equal to that character 

• By using if statement, you can check current substring length as i = start for the previous length of a required substring 

• Set the longest_len variable for storing the value length in the current substring with that of the previous substring. See if it is greater than the max() function

• Print the length of a longest substring with that of the substring itself

The time complexity in this case would be O [n] because you may need to traverse all characters. Though, the space complexity would be O[1] for both best and worst case.

Wrapping Up 

From longest palindrome substringto longest palindromic superstring to longest substring without repeating characters, you will come across the much wider concept of substring.

Keep this blog as your mentor to find the non repeating characters that exist in a longest substring.