Hi,

Yesterday, I had a technical interview round with Amazon Team. In this round, I asked to solve one famous DP problem with some modifications.

Problem Statement: Given three strings S, x, and y. You have to return interweaving positions of x and y in S with noise symbol positions (which are not part of x and y). Output format will be like this: [S1, S2, S3] where S1 = interweaving positions of string x in S, S2 = interweaving positions of string y in S, S3 = remaining characters (which is noise) positions.

We say that a string S is an interweaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequence s' and s'' so that s' is a repetition of x and s'' is a repetition of y. There might be some noise in S as well.

Look at the test cases for better understandings:

Test Case 1: Input: S = "101010101010101", x = "101", y = "010".
Output: Here, S is an interweaving of x and y, [101|010|101|010|101].
So, we need to return [{1,2,3|7,8,9|13,14,15}, {4,5,6|10,11,12}, {}]. Here 3rd set S3 is empty because there is no noise in S.

Test Case 2: Input: S = "000000010101010101010111", x = "101", y = "010".
Output: Here, also, S is an interweaving of x and y, ignoring leading noise and trailing noise [000000|010|101|010|101|010|111].
So, we need to return [{10,11,12|16,17,18}, {7,8,9|13,14,15|19,20,21}, {1,2,3,4,5,6,22,23,24}]

Test Case 3: Input: S = "100110011001", x = "101", y = "010".
Output: Here, also, S is an interweaving of x and y, [{1,2,4 | 9,11,12}, {3,5,6 | 7,8,10}, {}]

Note: You can ignore | symbol if you want. I couldn't come out with a solution. I know that simple DP problem which contains only x and y in S (without any noise, and |x|+|y| = |S|), but couldn't solve this problem.

Anyone can suggest a solution for the same ? Any help will be appreciated. Thanks in advance.