Largest substring which starts and ends with some substring This code is meant to find the length of the largest substring within a string that starts and ends with a given non-empty substring. Here are some examples:

strDist("catcowcat", "cat") → 9
strDist("catcowcat", "cow") → 3
strDist("cccatcowcatxx", "cat") → 9


This is based off this question.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def strDist(string, sub):
    if len(string) &lt; len(sub):
        return 0
    elif string[0:len(sub)] == sub and string[-len(sub):] == sub:
        return len(string)
    elif string[0:len(sub)] == sub and string[-len(sub):] != sub:
        return strDist(string[:-1], sub)
    elif string[0:len(sub)] != sub and string[-len(sub):] == sub:
        return strDist(string[1:], sub)
    elif string[0:len(sub)] != sub and string[-len(sub):] != sub:
        return strDist(string[1:-1], sub)


While the original question said that this should be done recursively, I would also be interested to see if there are any nice non-recursive ways of doing this. Also, let me know if a recursive or non-recursive approach would be preferable in an interview (assuming the question wasn't restricted to doing it recursively).

I think this algorithm is O(n) time complexity but O(n^2) space complexity. Correct me if I'm wrong. Also, any suggestions about how to improve complexities are welcome.
You should use str.startswith and str.endswith and avoid reinventing them with list slicing.

The conditions can be simplified: if the string does not start with the substring remove the first char if it does not end with the substring remove the last.

Space complexity can be reduced by passing indexes to the recursive invocations instead of copies of the string.