Comment by ninetyninenine

Thanks. Good solution.

I was thinking in terms of finding all subgraph isomorphisms. But this definitely is O(N) if all you need is one solution.

But then I thought about it even further and this reduces to sliding window problem. In this case you still need to travel to each node in the window to see if there’s a match.

So it cannot be that you traverse each node once. Not if you want to find all possible subgraph isomorphisms.

Imagine a string that is a fractal of substrings:

     rrrrrrrrrrrrrrrrrrrrrrrrrrrr

And the other one:

     rrrrrrr

Right? The sliding window for rrrrrrr will be 7 in length and you need to traverse that entire window every time you move it. So by that fact alone every node is traversed at least 7 times.