New update is available. Click here to update.

Problem

Submissions

Solution

New

Discuss

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 %

17 upvotes

Problem Statement

Suggest Edit

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

Auto

Console

Strings Notes

Left And Right Rotation Of A String

Shortest substring with all characters

Next smaller Palindrome

Longest Substring Without Repeating Characters

Anagram Difference

Match Specific Pattern

Minimum operations to make strings equal

Find K’th Character of Decrypted String

Anagram Substring Search

Uncommon Characters

Shortest substring with all characters

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-

Input Format:

Output Format:

Note:

Constraints:

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2: