[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 S′S′ 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 S′S′ such that AA is not a subsequence of S′S′.

If multiple such S′S′ exist, output any. If no such S′S′ 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 S′S′. If no such string exists, print −1−1.

[Coding] Broken Life solution codechef

• 1≤T≤10001≤T≤1000
• 1≤N,M≤1051≤N,M≤105
• Sum of NN over all test cases does not exceed 3⋅1053⋅105.
• Sum of MM over all test cases does not exceed 3⋅1053⋅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 S′S′ is equal to baba.

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

• ANSWER

  “Click Here“