Good Strings :
Difficulty Level : Medium
Submissions : 272
Asked In :
Marks :10
: 6 | : 0
You are given a string $$$s$$$ of length $$$n$$$, $$$q$$$ ranges of the form $$$l, r$$$ , and an array $$$arr$$$, containing permutation of numbers from 1 to $$$n$$$.
In one operation, you remove the first unremoved character as per the permutation. However the positions of the other characters will not change.
A string is considered good, if all the $$$q$$$ ranges have no repeated characters, after ignoring the removed ones. Please note that a range with all characters removed is also considered to be good.
Determine the minimum number of operations required to make the string good.
The first line contains two space separated integers $$$n$$$ and $$$q$$$. $$$(1 \le n,q \le 10^5)$$$
The second line contains the string $$$s$$$.
The third line contains $$$n$$$ space separated integers denoting the permutation $$$arr$$$.
The next $$$q$$$ lines contain 2 integers $$$l$$$ and $$$r$$$.$$$(1 \le l \le r \le n)$$$
Print an integer denoting the minimum number of operations required to make the string good.
5 2 aaaaa 2 4 1 3 5 1 2 4 5
2
8 3 abbabaab 6 3 5 1 4 2 7 8 1 3 4 7 3 5
5
For the first sample case, after 2 operations, the string will become "a.a.a" ('.' denote removed characters).
So the ranges $$$(1,2)$$$, and $$$(4,5)$$$ both contain single occurrence of 'a' Hence, the answer is 2.
