I don't really know if leetcode problems has the similar one, I tried to find a similar problem, but no results.
We have two opponents, and n rounds. The result of each round is either win or lose, no middle (ties). If the 1st player wins the round, we write 0, if the second one wins, then we write 1. In this problem tie is an interval, where amount of 0s == amount of 1s
We have to find the length of the longest sequence in array (which representing the results of each round), which gives us a tie. For e.g.
[0, 0, 1, 0, 1, 1, 1, 0, 0, 0] - answer will be 8, because [0, 0, 1, 0, 1, 1, 1, 0] will give us a tie (4 rounds for 1st player (count 0), 4 for second one (count 1)).
I came up with an O(n^2) solution, it is pretty naive and simple. But I feel that there is O(n) solution.
This is my O(n^2) solution.
All code written in Python.
def competition(s: list) -> int:
s = [-1 if i == 0 else 1 for i in s]
for i in range(len(s)):
summ = sum(s[i:])
if summ == 0:
return len(s[i:])I also came up with another idea, and it's working for some cases, where the sequence starts from the 1st round.
def competition(s: list) -> int:
count = [0, 0]
max_len = 0
for round in s:
count[round] += 1
if count[0] == count[1]:
max_len = sum(count)
return max_lenI guess if there is a O(n) solution, it would be pretty similar to KMP algorithm.