String Substitution Hard :
Difficulty Level : Hard
Submissions : 307
Asked In :
Marks :10
: 4 | : 2
You are given a string $$$S$$$ , and a list of strings which needs to be substituted in the input string $$$S$$$.
A substitution is a tuple $$$( L_i , R_i , subs_i ) $$$ which denotes that we need to substitute the substring $$$S[ L_i ... R_i ]$$$ with $$$subs_i$$$.
The intervals in this problem can be overlapping. Incase multiple substitutions overlap with each other , substitute the first substitution over minimum_L and maximum_R obtained across all overlapping substitutions.
You must find out the modified string $$$S_m$$$ after incurring all substitutions.
Example
Let S = "aaaaaaaaa"
Let subs = [ (4,6,"hi") , (1,2,"bye") , (2,5,"ohho") , (7,7,"hehe")];
When we reach at index i = 1 , we see that the range 1,2 overlaps 2,5 which overlaps 4,6 , Hence 1,2 indirectly overlaps 4,6 (which comes first based on index). The combined substitution becomes [ (1 , 6 , "hi") ] , The substitution string is always the string that has the comes from the least index across all overlapping substitution strings.
$$$S_m$$$ = "ahihehea"
First line contains a string corresponding to $$$S$$$
Second line contains a single integer N corresponding to the total number of substitutions
N lines are followed containing each tuple $$$( L_i , R_i , subs_i )$$$
Contraints
$$$ 1 \le |S| \le 100000 $$$
$$$ 1 \le |N| \le 1000 $$$
$$$ 1 \le L_i \le R_i \le |S| $$$
All characters in the string are either smaller case alphabetic characters or '_'
A single string $$$ S_m $$$ which corresponds to the modified string after all substitutions.
a_b_c_d_e_f_g 4 4 6 hi 1 2 bye 2 5 ohho 7 7 hehe
ahihehee_f_g
