1548 - SUFFIX

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 2

Solved: 2

Description
A string is a list of characters containing only letter ‘a’ to ‘z’. For example: “abcdefg”, “isun” are valid strings. “rocket323” is not a valid string.



A suffix of a string suf[i] is the list of characters at positions from i to n-1 (positions are labeled from 0 to n – 1, n is length of the string). For the string “hustacm”, suf[0] = “hustacm”, suf[1] = “ustacm”, suf[3] = “tacm”, suf[6] = “m”.



The suffix list L of a string is a permutation of numbers from 0 to n-1(n is length of the string), which satisfy the following condition: suf[L[0]] < suf[L[1]] < suf[L[2]] < … < suf[L[n-1]].



For the string “aabac”, its suffix list is [0, 1, 3, 2, 4].



Here comes the question: Given a string S and a suffix list L, you are to change minimum number of characters of S so that the suffix list of the new string is equal to L.
Input
There are multiple cases, for each case:

The first line is integer n representing the length of the string. (1 <= n <= 500)

The second line is the string.

The third line is a permutation of numbers from 0 to n-1.
Output
For each case, output the minimum number of characters to change in order to satisfy the condition above, if there is no solution, just output -1.
sample input
3
abc
0 1 2
3
aab
2 0 1
sample output
0
2
hint
source
Yang XiaoBin | 2011 Multi-University Training Contest 8 - Host by HUST
© 2015 HUST ACMICPC TEAM. All Right Reserved.