I'm trying to solve the USACO problem Censoring(Bronze), which was the 1st problem for the 2015 February contest. My solution works for some test cases, but then times out for the rest. How do I speed up the code? I tried to use Numba, but Numba doesn't work in USACO IDE. https://ide.usaco.guide/NXQs8hkV3sWOtNYsvyj http://www.usaco.org/index.php?page=viewproblem2&cpid=526 This is the problem link.
This is my code:
input = open('censor.in', 'r').read().split('\n')
s = input[0]
c = input[1]
l = len(c)
while True:
try:
i = s.index(c)
s = s[:i] + s[i + l:]
except:
break
output = open('censor.out', 'w')
output.write(s)
output.close()
It timed out for test cases 7-15. I expected it to run with O(n) time complexity because of the while loop, which should work, but it didn't. What's wrong?
Your code is not O(n) for two reasons. To see why, let's consider what I think is the worst case: The input is 500,000 as followed by 499,999 bs. And you're asked to delete ab.
Problem #1. You are starting your search for the next occurrence of ab from the beginning of the string. Each of your searches is going to be O(n), since you don't find ab until the middle of the string. If your previous search returned position i, you know that after collapsing the string, you don't need to go back further than i - len(search_string) + 1. You would have found a result at i - len(search_string) on the previous round.
Problem #2. String concatenation is O(n). You are repeatedly chopping out the middle of the string and putting the front and back together again. Again, you'll end up with an O(n^2) algorithm. I can't come up immediately with a simple way to fix this. A more complicated solution would be to put the string into a deque, but that complicates the search part of the code.
In any case, your code is not O(n). You have a single while loop, but you're doing more work than you realize inside each while loop.