Last Updated: 19 Nov, 2020
Longest Unique Substring ll
Easy
Asked in companies
You are given a string 'Str' consisting of 'N' lowercase Latin letters. You have to find the longest substring of the given string without repeating characters.
String ‘B’ is a substring of string ‘A’ if it can be obtained from ‘A’ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
For Example :
If the given input string is "aabc", then you should return "abc" as the longest substring without repeating characters.
Note :
If there are multiple substrings with the same length, then you should print the substring which comes earlier in the given string.
For Example :
If the given input string is "abcda", here “abcd” and “bcda” can be the longest unique substring but “abcd” comes earlier in the given string. So we will print “abcd” as the longest unique substring.
Input Format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
The first line of each test case contains a positive integer N, which represents the length of the string.
The next line contains a string consisting of lowercase Latin letters.
Output Format :
For every test case, print the longest unique substring.
The output of each test case is printed in a separate line.
Note :
Do not print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
Time Limit: 1 sec
Approaches
In this approach, we will consider every substring and check if it can be the longest unique substring. Let’s say we have a variable ‘ans’ that stores the longest unique substring.
For every substring, we will make a count array of size 26 that will store the count of each character in the substring. If every character in the substring has a count less than 2, we check if it is the longest unique substring encountered till now. If it is, we update ‘ans’ to store the value of this string.
Algorithm
- Run a loop to consider starting index of substring using a variable ‘i’.
- Run another loop to consider the ending index of substring using a variable ‘j’.
- Initialize an array ‘cnt’ and store the count of every character in substring from ‘i’ to ‘j’.
- If the count of every character is less than 1 and it is the longest substring found yet, store the substring in a string ‘ans’.
- Return ‘ans’.
We know that there are 26 characters in the lowercase Latin letters, so the longest unique substring can have at most 26 characters. We will iterate on the indices of the string and for each index, ‘idx’ do these steps.
Algorithm
- Make a count array of size 26 which stores the count of the characters, initially, all have count zero.
- Make two variables ‘maxLen’ and maxLenIdx, which will store the length of the longest unique string and index from which it starts respectively.
- Iterate on the indices from ‘idx’, until we find a character that has a count equal to 1 and change ‘maxLen’ and maxLenIdx accordingly.
- Return the substring starting from index maxLenIdx and having length ‘maxLen’.
The idea is to use sliding window technique. In sliding window technique we will maintain a window which contains unique characters. If we add a new character at the end of the window which is already present in it, then we have to remove characters from the beginning until the window contains unique characters.
We define the window as two pointers i and j, the window size is (j-i+1). We will initialize the pointers pointing to the first character in the string, then we will increment j if it violates the constraint and then accordingly, we will increment i. To store the count of characters in the window we will make an array of size 26 (number of lowercase Latin letters).
We will also make two variables maxLen and maxLenIdx, which will store the length of the longest unique string and index where it ends and for each window, we will update these variables accordingly.
Return the substring ending at index maxLenIdx and having length maxLen.