Shortest substring with all characters

Moderate
0/80
Average time to solve is 18m
profile
Contributed by
25 upvotes
Asked in companies
AmazonMicrosoftCisco

Problem statement

You have been given a string 'S' which only consists of lowercase English-Alphabet letters.

Your task is to find the shortest(minimum length) substring of 'S' which contains all the characters of 'S' at least once. If there are many substrings with the shortest length, then find one which appears earlier in the string i.e. substring whose starting index is lowest.

For example-
If the given string is S = "abcba", then the possible substrings are "abc" and "cba". As "abc" starts with a lower index (i.e. 0, "cba" start with index 2), we will print "abc" as our shortest substring that contains all characters of 'S'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The only line of input contains a string 'S' i.e. the given string.
Output Format:
The only line of output contains a string i.e. the shortest substring of 'S' which contains all the characters of 'S' at least once.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= N <= 10^5
'S' only contains lowercase English-Alphabet letters.

Where 'S' is the given string and ‘N’ is the length of ‘S’.

Time Limit: 1 sec 
Sample Input 1:
aabcabb
Sample Output 1:
abc
Explanation of Sample Input 1:
Some of the possible substrings are "aabcabb", "aabc", "abcab", "abc", etc. Out of all these substrings, we will have "abc", "bca" and "cab" with the shortest length. As "abc" appear earliest in the string, we will print "abc" in the output.
Sample Input 2:
cddeyys
Sample Output 2:
cddeyys
Hint

Count distinct characters in the string and check all possible substrings naively.

Approaches (2)
Naïve Solution

The problem boils down to counting distinct characters that are present in the string and then finding the minimum length substring that contains this many distinct characters at least once.

 

We can naively check all substrings by two nested loops and maintain a count of distinct characters for each substring with the help of a hashmap. There are many methods for maintaining this count with a hashmap like the size of the hashmap, or maintaining the ‘count’ variable, etc. 

 

Whenever the count of distinct characters for a substring equals the count of distinct characters in the given string, we process this substring. We will choose the minimum length substring out of all these substrings.

Time Complexity

O(N ^ 2),  where ‘N’ is the length of the string.

 

We will run two nested loops for checking all the N*(N+1)/2 substrings of the given string and hashmap operations take constant time.

Space Complexity

O(K), where K is the number of distinct characters in the string.

 

We are using two hashmaps and their size will not exceed the count of distinct characters in the string. 

Code Solution
(100% EXP penalty)
Shortest substring with all characters
Full screen
Console