Hint: Try thinking about the problem in reverse.

Solution: Thinking about the problem in reverse, we start with \(S\). If there is a substring that equals \(T\), our last operation might have been at that position. Let’s assume it is; what would be the state of \(S\) before that operation? Well, the \(T\) substring might have replaced any characters. Let’s put a placeholder “wild” character ? in those positions. What moves do we have left? It turns out we could be able to find additional \(T\) substrings, where zero or more of the characters of \(T\) substring have been replaced with the wild character, and that could have been the second-last operation; continuing on, if we are able to make every character the wild character this way, the answer is yes. We can also see that making a “move” in this reversed problem is never harmful, so if we can’t make any moves, the answer is no.

Let’s name the “moves” by their left index, so “move \(x\)” becomes “replace characters \(S[x : x + M - 1]\), which should match \(T\), with the wildcard”

How do we quickly check whether we can make any moves? We could scan for the first move in \(O(NM)\), but whenever we find and make move \(x\), it might have made moves anywhere from \(\max(1, x - M + 1)\) to \(\min(x + M - 1, N - M + 1)\) possible due to the new wildcards. What we should do is either use a stack or recursion, much like depth-first search, so that whenever we make a move, we recheck these positions to see if there are any possible new moves. Also note that if \(S[x : x + M - 1]\) are all already wildcards, it is pointless to make move \(x\), so we should skip it to avoid an infinite loop.

The final time complexity is \(O(NM^2)\) or \(O(NM)\) depending on implementation; it should pass regardless.

Bonus: Instead of a stack, you could use only an integer value / pointer to represent positions that still need to be checked, because we could assume that “\(\text {pointer} = x\)” means that all positions \(\geq x\) need to be checked. So if we find a match, we rewind the pointer by up to \(M-1\) steps, otherwise we advance the pointer one step.