is there a faster way to make this code faster?

March 21, 2022

So we were tasked to make the code below faster, as there are examples for the code where it will need an input of very large strings, any help will do.

import sys

a = input()
b = input()

strs = ''
i = 0

for i in range(len(a)):
    elif b[i] in a:
        strs = strs + 'b'
    i = i + 1

print(strs)

>Solution :

The following function will do the job with the key change being using a set() instead of a list which will decrease the runtime from O(len(a) * len(b)) to O(len(a)).

Some other changes are some checks on array length which you need to do to be sure your index will not be out of bounds of the array.

import sys

# what do you need z for?
# this will only cause problems, you can use len() instead to get the lenght of the string
# z = int(input())
a = input("Please enter string a: ")
b = input("Please enter string b: ")


def compare_strs(a, b):
    strs = ''
    # no need for this here as range will start at 0 by default
    # i = 0
    # set will have constant lookup time O(1)
    lookupCharacters = set(a)
    for i in range(len(a)):
        # you need to make sure the index is in bounds of the array here!
        if i < len(b):
            if b[i] == a[i]:
                strs = strs + 'a'
            # this will now lookup in the set which takes O(1) and not O(len(a))
            elif b[i] in lookupCharacters:
                strs = strs + 'b'
        strs = strs + 'c'
        # no need for this here as range() will automatically increase i for the next iteration
        # i = i + 1
    sys.stdout.write(strs)


compare_strs(a, b)