12868번 - 문자열 찾기

길이가 N인 문자열 S에서 인버젼의 개수는 S[i] > S[j]이면서 0 ≤ i < j < n을 만족하는 (i, j) 쌍의 개수와 같다. 문자열의 첫 번째 글자는 0번째 글자이다. 예를 들어, "abcab"의 인버젼의 개수는 3개 (1, 3), (2, 3), (2, 4) 이다.

정수 N과 V, 그리고 문자열 S이 주어진다. 이때, 알파벳 소문자 처음 N개의 순열로 이루어진 모든 문자열 중에서 다음 조건을 만족하는 문자열 R 중에서 사전 순으로 가장 앞서는 문자열을 찾으려고 한다. 즉, R은 길이가 N이며, 알파벳 소문자 처음 N개로 이루어진 문자이며, 각 알파벳은 한 번씩 사용할 수 있다.

• 문자열 R에 있는 인버젼의 개수는 V보다 크거나 같아야 한다.
• 문자열 R은 문자열 S보다 사전순으로 앞서지 않아야 한다.

첫째 줄에 N (1 ≤ N ≤ 20)이 주어진다.

둘째 줄에 V (0 ≤ V ≤ N×(N-1)/2)가 주어진다.

셋째 줄에 문자열 S가 주어진다. S는 알파벳 소문자 처음 N개중 일부로 이루어져 있다. S를 이루고 있는 알파벳은 중복되지 않는다.

첫째 줄에 문제의 조건에 해당하는 문자열 R을 출력한다. 만약, 가능한 R이 없는 경우에는 -1을 출력한다.