Longest Unique Substring ll

Easy
0/40
profile
Contributed by
3 upvotes
Asked in companies
Goldman SachsIntuitAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
3
6
abccaa
2
cdedc
5
aaaaa
Sample Output 1 :
abc
cde
a
Explanation for Sample Input 1 :
In the 1st test case, “abc” is the longest unique substring.

In the 2nd test case, “cde” and “edc” are the longest substrings but “cde” comes earlier in the given string.

In the 3rd test case, “a” is the longest unique substring.
Sample Input 2 :
2
4
abcd
3
aba
Sample Output 2 :
abcd
ab
Hint

For each substring, check if it can be the longest unique substring.

Approaches (3)
Brute-Force

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’.
Time Complexity

O(N^3), Where N is the size of the given array.
 

It takes O(N^2) to consider every substring and in the worst case, it will take O(N) time to check if a substring contains unique characters or not. Thus, the final time complexity is O(N * N * N) = O(N^3).

Space Complexity

O(1)
 

Since the size of the count array is 26 and the maximum size of the longest unique string can be 26 ( as there are a maximum of 26 distinct characters ), thus the final space complexity is O(2 * 26) = O(1). 

Code Solution
(100% EXP penalty)
Longest Unique Substring ll
Full screen
Console