Fighting Game

Moderate

0/80

Average time to solve is 15m

Contributed by

0 upvote

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1

1
3

Explanation for Sample Input 1:

For case 1:
There are multiple Combos that occur in both rounds, including [5], [7], [8] and [9]. The length of all of these is 1, so the answer would be 1.

For Case 2:
The Combo [3, 5, 5] occurs in both rounds and is also the longest such Combo. Hence, the answer is 3.

Sample Input 2:

Sample Output 2:

0
2

Hint 1

Hint 2

Try computing the longest common Combo starting from all pairs of indices.

Approaches (2)

Approach 1

Approach 2

Brute Force

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’
Return ‘ans’

Time Complexity

O (N * M * min(N,M)), where N is the size of A and M is the size of B.

For each of the N*M pairs, we extend the Combo as long as possible. Hence, the overall complexity is O(N * M * min(N, M)).

Space Complexity

O(1), as we only use constant space.

(100% EXP penalty)

Fighting Game

Console