Approach 1: Ad-Hoc
If we see say
S == 'I', we can always put
0 as the first element; similarly, if we see
S == 'D', we can always put
N as the first element.
Say we have a match for the rest of the string
S, S, ... using
N distinct elements. Notice it doesn't matter what the elements are, only that they are distinct and totally ordered. Then, putting
N at the first character will match, and the rest of the elements (
1, 2, ..., N or
0, 1, ..., N-1) can use the matching we have.
Keep track of the smallest and largest element we haven't placed. If we see an
'I', place the small element; otherwise place the large element.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.