All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Two types of queries
/

Data Structures, Disjoint Data Structures

Problem
Editorial
Analytics

You are given a string str. It costs one unit of a coin to change a character at an index. Your task is to convert it into a palindrome with minimum coins. Also, you are given \(q\) number of queries. The queries are of the following types:

  • 1 A B
  • 2

After solving the first type of query, you can convert character \(A\) into character \(B\) without any cost and vice versa. In the second type of query, you are required to answer the minimum cost that is required to convert the given string into a palindrome.

Note: If character \(A\) can be converted to character \(B\) and character \(B\) can be converted to character \(C\), then you can convert character \(A\) to character \(C\).

Input format

  • The first line contains \(n\) denoting the length of the string.
  • The second line contains string str.
  • The third line contains \(q\) that denotes the number of queries.
  • The next \(q\) lines contain one of the mentioned queries.

Output format

For each query of type 2, print the minimum cost to convert a given string into a palindrome.

Constraints

\(1 \le n \le 10^5\)

\(1 \le q \le 10^5\)

The string consists of only lowercase letters.

 

SAMPLE INPUT
10
vwuhjdbgzp
4
1 a b
2
1 w z
2
SAMPLE OUTPUT
5
4
Explanation

After the first query, a can be converted to b.  

In the second query, all the pairs cost 1 unit for making the palindrome.

After the third query, w can be converted into z or vice-versa with zero cost.

In the fourth query, since z can be converted to w in 0 cost, total cost is equal to 4.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?