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.
You know how to do it when there is no noise right, so let's form the solution of new from the old one only. When there is no noise then for every character you have two options either it belongs to X or to Y but now if u see in the modified version, you will notice that there is one more option of noise where a character can go to. Atlast for every character u have three options, either it belongs to X or Y or Noise. Dp[X_cnt][Y_cnt][Noise_cnt] State will look like this. I hope u got the intuition.