Question
Minimal Swap Cost for Lex Order
You're given a string s of length n and a cost array cost[] of size n - 1. You may swap any adjacent characters. The cost to swap characters at index i and i + 1 is cost[i].
Your task is to return the minimum total cost required to make the string sorted in lexicographical order.
Hint: Think about how sorting algorithms like bubble sort work when only adjacent swaps are allowed. How can you adapt this idea while considering the cost of each swap?
Input
First line: Integer n — length of the string
Second line: String s of length n
Third line: n – 1 space-separated integers representing the cost[] array
Second line: String s of length n
Third line: n – 1 space-separated integers representing the cost[] array
Output
Print a single integer — the minimum total cost required to make the string lexicographically sorted
Example
Input:
4
dcab
1 3 2
Output:
4
Explanation:
One possible sequence of swaps:
Swap c and a (cost = 2) → "dcab" → "dabc"
Swap d and a (cost = 1) → "dabc" → "adbc"
Swap d and b (cost = 1) → "adbc" → "abdc"
Swap d and c (cost = 2) → "abdc" → "abcd"
Total cost: 4
4
dcab
1 3 2
Output:
4
Explanation:
One possible sequence of swaps:
Swap c and a (cost = 2) → "dcab" → "dabc"
Swap d and a (cost = 1) → "dabc" → "adbc"
Swap d and b (cost = 1) → "adbc" → "abdc"
Swap d and c (cost = 2) → "abdc" → "abcd"
Total cost: 4