New update is available. Click here to update.

# Shortest substring with all characters

Contributed by
Amandeep Kaur
Last Updated: 23 Feb, 2023
Medium
0/80
Avg time to solve 18 mins
Success Rate 85 %
Share

## Problem Statement

Suggest Edit

#### 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 )
##### 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
``````
Auto
Console