Mark As Completed Discussion

As you can see, there are total 15 comparisons for the given test case. This is not close to the linear 6 comparison time complexity. In fact, this is a complexity of close to 6*3 comparisons. The reason for this is for each starting letter of the main string, we are comparing the whole substring and then resetting back to the initial character. See the image below:

Complexity Calculation

So the time complexity will be O(mn) where m and n are the lengths of the string and substring. For memory, using the two-pointer method, we use a constant O(1) space for our solution.

There is another established algorithm named Rabin-Karp algorithm which uses hashing and two-pointer technique to solve this problem in O(n) time complexity. Feel free to try to implement that algorithm and tell us in the discussion about it.