How can I optimize this hash string function? I'm writing a function which gets two strings and a number k as an input, and outputs a string with length k which is present in both strings.  I want to do this using the function hash_sequence().

I need my code to be as efficient as possible because my inputs are very large strings.

def hash_sequence(string, k):

    dictionary={}
    for i in range(len(string)-(k-1)):
        triplet = string[i:i+k]
        dictionary.setdefault(triplet,[]).append(i)
    return dictionary




def intersects(string1, string2, k):
    itr=min(len(hash_sequence(string1,k)),len(hash_sequence(string2,k)))
    for i in range(itr):
        if list(hash_sequence(string1,k))[i] in hash_sequence(string2,k):
            return list(hash_sequence(string1,k))[i]
    return None
Your hash_sequence() function is quite good. The only thing I would suggest about that function is rename your triplet variable to something more suitable like sequence. Currently, I expect triplet to contain strings of length 3. A name like sequence is more general and is a better representation of what will be stored in it.

Your intersects() function is where the vast improvement can be found. Each iteration of the for loop you are re-running the hash_sequence() function. If your strings are really long and k really small (i.e. 1), hash_sequence() would have to scan through the entirety of both strings each iteration of the loop!

Instead, we only have to hash one of the strings! Before the loop save the returned dict to a variable (this way the hash_sequence function is only ran once):

def intersects(string1, string2, k):
    dictionary= hash_sequence(string1, k)


Next, instead of iterating over the length of the dicts we can iterate over the keys in the dict, then we can check if that key is 'in' the other string:

for key in dictionary:
    # Check if the key (string of length k) is in the other string
    if key in string_two:
        return [key]




Here is my full version of your code:

def hash_sequence(string, length):
    dictionary = {}
    for i in range(len(string) - (length-1)):
        sequence = string[i:i+length]
        dictionary.setdefault(sequence, []).append(i)

    return dictionary

def intersects(string_one, string_two, length):
    dictionary = hash_sequence(string_one, length)

    for key in dictionary:
        if key in string_two:
            return [key]
    return None




As a final note, take a look at PEP8, the official Python style conventions. It will help make your code more Pythonic.