class Solution:
def maxNumOfSubstrings(self, s: str) -> List[str]:
"""
main idea: this is a finding list of minimal non-overlapping interval problem. In order to avoid sorting(based on index), we use a left, right varible to track range for each char. And then use greedy to get the minimal length for each non-overlapping intevals
tc O(N) sc O(26)=>O(1)
1. preprocess s, get first occurance index and last
2. loop through string s, get its first and last index and check between first - last, if there is a different char appeared earlier than target char
if yes, target char will not be ideal candidate
if no, check if its last occurance out of target char's last occurance (1) if yes, extend target char's last position (2) if no, overwriting within target ranges optimal substring
3. for each target char, check if its updated right range before current position, if yes, a new subtring candidate occurs ; otherwise we just keep updating the most minimal length subtring without overlapping
4. return res list after whole loop is over
"""
d = {} # char: [left,right]
for i,c in enumerate(s):
if c not in d:
d[c] = [i,i]
d[c][1] = i
res = []
def get_new_right(i,s):
l,r = d[s[i]]
new_right = r
j = i
while j < new_right+1: # keep updating new_right boundry , can't use for
if d[s[j]][0] < l:
return -1
new_right = max(d[s[j]][1],new_right)
j += 1
return new_right
last_subs_right = -1
for i in range(len(s)):
l,r = d[s[i]]
if i == l:
n_right = get_new_right(i,s)
if n_right != -1:
if last_subs_right < i : # right < l => right points at last substring's right boundry
res.append('')
last_subs_right = n_right
res[-1] = s[i:last_subs_right+1]
return res