Hi all,

I am a novice coder and tried participating in the recent contest. I tried the easy problem but kept getting Time Limit Error. From my understanding, the problem is of O(N) time complexity. I found solutions of O(NlogN) that got submitted. Would really appreciate if someone could tell me why is this code getting me TLE?

Here's my code for the Helvetic Coding Contest 2024, May 4th (Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)), Problem A1 Balanced Shuffle (Easy):

import collections
input = input()
dct = collections.defaultdict(list) #key is prefix_balance, val is a list of idx
prefix_balance = 0
for i in range(len(input)):
        dct[prefix_balance].append(input[i])
        if input[i]=='(':
                prefix_balance += 1
        else:
                prefix_balance -= 1




ans = ""
for (prefix, val_lst) in dct.items():
        val_lst.reverse()
        val_string = "".join(val_lst)

        ans += val_string
print(ans)