## sobby

BAN USER- 0of 0 votes

AnswersSmallest string

- sobby in India

You are given the following :

1. Two strings S and T each of Length N

2. K Pairs of integers L(i) and R(i) (0 <= l(i) < R(i) <= N-1)

You can perform any of the following two operations any number of time.

1. You can replace the character of string S at the ith position with the character of string T at the ith position

2. You can select from any provided K pairs and you are allowed to swap characters at position L(i) and R(i) in string T

Now, you are required to perform all the operations optimally so that string S can be lexographically smallest.

All characters of S and T are of lowercase English letters and there are only two ways to perform all the operations either(111...1) then (2222...2) or (2222...2) then (1111.1)

Input Format :

1. First line contains number of test cases:

2. Second line contains the lengths of string and the number of pairs of integers.

3. Next two line contains S and T two strings.

4. The next K lines contains the space separated integers.

Sample Input :

1

8 4

abagfiab

cbacbcda

0 1

1 2

3 4

4 5

sample output : aaabccaa| Report Duplicate | Flag | PURGE

PayPal SDE-3 Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.