[Coding] Broken Life solution codechef

[Coding] Broken Life solution codechef

 

You are given two strings SS and AA of lengths NN and MM respectively.

  • String SS contains characters from the set {?, a, b, c, d, e}{?, a, b, c, d, e}.
  • String AA contains characters from the set {a, b, c, d, e}{a, b, c, d, e}.

Let SS′ denote the string formed by replacing all the ?? in SS using the characters from the set {a, b, c, d, e}{a, b, c, d, e}.
Construct SS′ such that AA is not a subsequence of SS′.

If multiple such SS′ exist, output any. If no such SS′ exists, print 1−1.

[Coding] Broken Life solution codechef

  • The first line will contain TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains two integers NN and MM – the lengths of strings SS and AA respectively.
  • The second line of each test case contains string SS.
  • The third line of each test case contains string AA.

Output Format

For each test case, output any valid string SS′. If no such string exists, print 1−1.

[Coding] Broken Life solution codechef

  • 1T10001≤T≤1000
  • 1N,M1051≤N,M≤105
  • Sum of NN over all test cases does not exceed 31053⋅105.
  • Sum of MM over all test cases does not exceed 31053⋅105.

Sample Input 1 

2
4 2
?ab?
ba
4 2
a??b
ab
[Coding] Broken Life solution codechef  
aabe
-1

Explanation

Test case 11: Replace the ?? at indices 11 and 44 using characters aa and ee respectively. Both the characters belong to the set {a, b, c, d, e}{a, b, c, d, e}.
The string S=aabeS′=aabe. Note that no subsequence of SS′ is equal to baba.

Test case 22: There is no possible value of SS′ such that abab is not a subsequence of SS′.

Leave a Comment