Getting WA and TLE in Not All Flavours

,
1

This is the code I used. Passes the test cases but WA and TLE in hidden test cases

def longest_sub():
    n, k = map(int, input().split())
    flavours = list(map(int, input().split()))
    for i in range(n-1):
        for j in range(n-1, 0, -1):
            c = len(set(flavours[i:j+1]))
            if c < k:
                return len(flavours[i:j+1])


for i in range(t):
    print(longest_sub())
2

You have two loops with n items and you build a set with up to n elements inside that loops so the time complexity is O(n^3), it will get TLE by sure.
The WA comes from:

  • your j could be smaller than i, that is not correct
  • you return as soon as c<k but that doesn’t need to be the largest subsegment; larger segments can be found starting from other i
3 Likes
3

Thank you. I’m so dumb.