Last Updated: 3 Dec, 2021
Fighting Game
Moderate
Asked in company
Bruh loves playing fighting games, and in each round he performs a series of moves, where each move is represented by an integer between 1 and 10^9. A sequence of one or more continuous moves is called a “Combo”. He just played two rounds and now wants your help to find the length of the longest Combo which occurred in both the rounds he played.
For example, if the moves in the first round were [8,7,5,7,9] and the moves in the second round were [6,5,7,9,1], the longest combo which occurred in both rounds would be [5,7,9].
Note: It is possible for a Combo to contain the same move multiple times.
Input Format:
The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains two space separated integers 'N' and ‘M’, denoting the number of moves in the first and second game respectively.
The second line contains an array 'A' of length 'N', denoting the moves of the first game.
The third line contains an array 'B' of length 'M', denoting the moves of the second game.
Output Format:
For each test, print an integer, denoting the length of the longest Combo which occurred in both rounds.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= T <= 10
1 <= N,M <= 10^3
1 <= A[i] <= 10^9, i ∈ (1,N)
1 <= B[j] <= 10^9, j ∈ (1,M)
Note -
The sum of 'N' and ‘M’ over all test cases does not exceed 2000.
Time Limit: 1 sec
Approaches
Approach: For all ‘i’ ∈ (1, ‘N’) and ‘j’ ∈ (1,’M’), we compute the longest possible Combo starting from ‘i’ and ‘j’. We can use two pointers and keep extending them until there is a mismatch. The maximum of all these lengths computed will be the final answer.
Algorithm:
- Initialise ‘ans’ with 0
- Iterate a loop with ‘i’ = 1 to ‘N’
- Iterate a loop with j = ‘1’ to ‘M’
- Initialise ‘k’ with 0
- While ‘A[i+k]’ and ‘B[i+j]’ match, increment ‘k’ by 1
- Else, break
- ‘k’ is currently the length of longest Combo starting at ‘i’ and ‘j’
- If ‘k’ > ‘ans’
- Assign ‘ans’ = ‘k’
- Iterate a loop with j = ‘1’ to ‘M’
- Return ‘ans’
Approach: Let dp[i][j] represent the length of the longest Combo ending at index ‘i’ of A and index ’j’ of B. If A[i] is equal to B[j], we can extend the Combo ending at (i-1,j-1) by 1 such that it now ends at (i,j). This gives us the recurrence relation:
If A[i] == B[j]: dp[i][j] = 1 + dp[i-1][j-1]
Else: dp[i][j] = 0;
The answer will be maximum of dp[i][j] for all ‘i’ ∈ (1,N) and ‘j’ ∈ (1,M)
Algorithm:
- Initialise ‘ans’ with 0
- Create a 2D ‘dp’ array of size N * M, and initialise all elements with 0.
- Iterate a loop with ‘i’ = 1 to ‘N’
- Iterate a loop with j = ‘1’ to ‘M’
- If A[i] is equal to B[j]
- dp[i][ j] = 1 + dp[i-1][j-1]
- If dp[i][j] > ‘ans’
- Assign ‘ans’ = dp[i][j]
- If A[i] is equal to B[j]
- Iterate a loop with j = ‘1’ to ‘M’
- Return ‘ans’