Mark As Completed Discussion

One Pager Cheat Sheet

  • Write a function detectSubstring to detect a substring within a given string, avoiding String class's built-in substring or substr method, with O(n) time complexity and O(1) space complexity, and handle strings of length ≤ 100000.
  • We should reason out what we need to do before diving into the logic of solving a simple example like whether a car is in carnival.
  • We can use the two-pointer technique to compare two strings and check if one is a substring of the other by writing a for-loop to compare the characters at each index and discover how far we can extend our match when we find an initial one.
  • We can use an idxOfStart variable and a j index to determine if a string contains a substring by checking character-by-character whether they match or not.
  • The code needs two slight adjustments to handle duplicate characters and accurately obtain the index of the start of matches, and its complexity is more accurately expressed as O(n*m), where m is the length of the substring.
  • The number of comparisons made for the given code in the given test case is 12, which is n * m (6 * 3).
  • With the two-pointer method, the time complexity for solving the given test case problem is O(mn) and a constant O(1) space is used, although the Rabin-Karp algorithm may provide a more optimal O(n) time complexity solution.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

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

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.