Company: trading tech_17sep
Difficulty: medium
Minimal Substring Split Problem Description You are given a string consisting of lowercase letters of the English alphabet. You must split this string into a minimal number of substrings in such a way that no letter occurs more than once in each substring. For example, here are some correct splits of the string 'abacdec': ('a', 'bac', 'dec'), ('a', 'bacd', 'ec') and ('ab', 'ac', 'dec'). Write a function: def solution(S) that, given a string S of length N, returns the minimum number of substrings into which the string has to be split. Examples Example 1: Input: S = "world" Output: 1 Explanation: There is no need to split the string into substrings as all letters occur just once. Example 2: Input: S = "dddd" Output: 4 Explanation: The result can be achieved by splitting the string into four substrings ('d', 'd', 'd', 'd'). Example 3: Input: S = "cycle" Output: 2 Explanation: The result can be achieved by splitting the string into two substrings ('cy', 'cle') or ('c', 'ycle'). Example 4: