String Partition
MediumPractice library · +20 XPstringshashingprefix sums
Given a string S consisting of lowercase English letters, partition it into the minimum number of contiguous substrings such that each substring appears at most once in the partition. You should print this minimum number of substrings.
Input
A single line containing the string S.
Output
A single integer representing the minimum number of substrings.
Constraints
1 <= length of S <= 200000.
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
abcabc
Output
1
Partition into "abc", "abc". Minimum 2 substrings.
Example 2
Input
aaaaa
Output
1
Partition into "a", "a", "a", "a", "a". Minimum 5 substrings.
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
abcabc
Example 2 input
aaaaa