Given n, an integer representing the length of a binary string a, which is all '0's in the beginning.

Also given operations, an array of strings, each representing an operation of one of these two types:

L: Find the smallest index with 0 and replace the character at that index with 1

C{index}: given like C0, C1 or C50 etc..., Replace the character at index(given after C in the command) to 0.

example of operations array: [L, L, C0, L , C3]

Time limit given was 3 seconds to run the test cases.

I had 12 cases passing and rest were timed out. (It is a question from a coding exam)

Here is my solution, please suggest me what I could have changed to get all the testcases passed.

a = ""
for i in range(n):
    a = a   "0"

for x in operations:
    if x == "L":
        a = a.replace("0", "1", 1)
    if "C" in x:
        a = a[0:int(x[1:])]   "0"   a[int(x[1:]) 1:]
return a

The test cases for which time limit exceeded were hidden testcases, So I could not provide the testcases here.

Thank you for the help.

CodePudding user response：

I think there are several approaches you can use to improve the code performance. The first is as @Mahrkeenerh mentioned, which would be to use a list of char instead of str so that it would be more efficient to replacing value based on the input index. The second would be to use heapq built-in library to create a heap data structure to store a list of indices that are zeros (zero_indices in the below code). The benefits of using this list is that you can get the smallest indices in the zero_indices with O(1) time complexity instead of O(n) when using regular for loop search (more details here). So when you get the L operation, you just need to pop the smallest number in zero_indices and set the index value to '1' in alist. When you get the C<n> operation, you need to extract the index, assign that index in a list to be 0 and add the new index to the zero_indices (performance would be O(logn)).

Overall, the performance of this approach would be O(m(logn)) where m is the number of operations and n is the length of string. This is more efficient than the original approach, which is O(mn)

import heapq

a = ['0'] * n
zero_indices = list(range(n))

for x in operations:
    if x == "L":
        # Pop the smallest index in zero_indices list O(1)
        a[heapq.heappop(zero_indices)] = '1'
    if "C" in x:
        index = int(x[1:])
        a[index] = '0'
        # Insert new zero index into the list O(log(N))
        heapq.heappush(zero_indices, index)

return "".join(a)

CodePudding user response：

Simple answer, by remembering the position of the first 0:

def main(n, ops):
    l = ["0"] * n
    first_zero = 0
    for op in ops:
        if op[0] == "L":
            l[first_zero] = "1"
            first_zero  = 1
            # Find the next 0
            for i, c in enumerate(l[first_zero:]):
                if c == "0":
                    first_zero  = i
                    break
        else:
            to_replace = int(op[1:])
            l[to_replace] = "0"
            first_zero = min(first_zero, to_replace)
    return "".join(l)


n = 5
operations = ["L", "L", "C0", "L", "C3"]
print(main(n, operations))
# 11000