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.

xxxxxxxxxx

}

var assert = require('assert');

​

function detectSubstring(str, subStr) {

  let idxOfStart = 0,

    j = 0;

​

  for (i = 0; i < str.length; i++) {

    // if match, compare next character of subStr with next of string

    if (str[i] == subStr[j]) {

      j++;

      if (j == subStr.length) {

        return i - (subStr.length - 1);

      }

    } else {

      i -= j;

      j = 0;

    }

  }

​

  return -1;

}

​

// console.log(detectSubstring('ggraph', 'graph'));

// console.log(detectSubstring('geography', 'graph'));

// console.log(detectSubstring('digginn', 'inn'));

​

try {

  assert.equal(detectSubstring('thepigflewwow', 'flew'), 6);

​

  console.log(

    'PASSED: ' + "`detectSubstring('thepigflewwow', 'flew')` should return `6`"

  );

Great job getting through this. Let's move on.

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