Most Frequent Substring
MediumPractice library · +20 XPstringshashingcounting
Given a string S, find the length of the shortest substring that contains every character present in S at least once. If multiple such substrings exist, return the length of the shortest one.
Input
A single line containing the string S.
Output
A single integer representing the length of the shortest substring containing all unique characters of S.
Constraints
1 <= |S| <= 200000. S consists of lowercase English letters ('a'-'z').
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
abacaba
Output
3
Unique chars are 'a', 'b', 'c'. Shortest substring containing all is 'bac' (length 3).
Example 2
Input
aab
Output
2
Unique chars are 'a', 'b'. Shortest substring is 'ab' (length 2).
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
abacaba
Example 2 input
aab