pattern of distinct integers and an array sequence that may contain repeats.
In one operation you may insert any integer into sequence at any position, including the very beginning or the very end.
Return the fewest insertions after which pattern becomes a subsequence of sequence, meaning it can be obtained from sequence by crossing out some elements without reordering the rest.pattern=[7, 2, 9], sequence=[2, 5, 9, 7] → 1
sequence already has 2 and 9 in the right order. Inserting 7 at the very front is enough: [7, 2, 5, 9, 7].
pattern=[4, 1, 6], sequence=[4, 8, 1, 1, 6] → 0
The pattern can already be read in sequence by skipping the 8 and one of the 1s.
pattern=[1, 2], sequence=[3, 3] → 2
No values in common, so both have to be inserted.
len(pattern), len(sequence) ≤ 10⁵pattern[i], sequence[i] ≤ 10⁹pattern are distinctpattern=[7, 2, 9], sequence=[2, 5, 9, 7]
1
Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.