Mark As Completed Discussion

There are still two slight issues with this code. Can you see what they are?

Let's take the examples of a string ggraph and substring graph. On the first iteration, g will match g, which is what we want. However, on the next iteration, we will try to match the second g in ggraph with r in graph.

What should happen is if we don't find a match, we ought to reset i a bit as well-- this is to accommodate duplicate characters. We can reset it specifically to the length of the last processed substring (or j).

The other thing is regarding the index of the start of the match-- we can simply get it from i - (subStr.length - 1). Note that you need to subtract 1 from the substring's length in order to get to the correct index.

Complexity of Final Solution

Let n be the length of the string. In the worst-case scenario, we iterate through all n characters of the string and do not find a match. Many of us will then declare that the time complexity is linear O(n). But think carefully, for each partial matching of substrings, we are traversing through the substring, and then again resetting to the initial pointer i.

To get a more clear insight into this, let's consider an example:

TEXT
1str = "aaaaaa"
2subStr = "aab"

The final solution code of the method explained above is given.

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment