Substring Search Patterns in DSA Javascript

Mental Model

We look through a big string to find if a smaller string appears inside it, step by step.

Analogy: Like scanning a long book page to find a specific word by checking each letter one by one.

Big string: H -> e -> l -> l -> o ->   -> W -> o -> r -> l -> d -> null
Small string:   W -> o -> r -> l -> d -> null
↑ scanning position

Dry Run Walkthrough

Input: big string: 'hello world', search substring: 'world'

Goal: Find if 'world' appears inside 'hello world' and where it starts

Step 1: Start checking from index 0 of big string

big: h[e]llo world
sub: world
checking 'hello' vs 'world'

Why: We must start from the beginning to find the substring

Step 2: Compare substring letters with big string letters at index 0

big: h[e]llo world
sub: w[o]rld
mismatch at first letter

Why: First letters differ, so substring not found here

Step 3: Move to index 1 in big string and compare again

big: h e[l]lo world
sub: w[o]rld
checking 'ello ' vs 'world'

Why: Try next position to find substring

Step 4: Mismatch found again, move to index 6 where 'w' is

big: hello [w]orld
sub: [w]orld
first letters match

Why: Found first letter match, check rest of substring

Step 5: Compare all letters of substring with big string starting at index 6

big: hello world
sub: world
all letters match

Why: Full substring matched inside big string

Result:

hello world
       ↑ substring 'world' found starting at index 6

Annotated Code

DSA Javascript

class SubstringSearch {
  static search(big, sub) {
    const n = big.length;
    const m = sub.length;
    for (let i = 0; i <= n - m; i++) {
      let j = 0;
      while (j < m && big[i + j] === sub[j]) {
        j++;
      }
      if (j === m) {
        return i; // substring found at index i
      }
    }
    return -1; // substring not found
  }
}

// Driver code
const bigString = 'hello world';
const subString = 'world';
const index = SubstringSearch.search(bigString, subString);
if (index !== -1) {
  console.log(`${bigString}\n${' '.repeat(index)}↑ substring '${subString}' found starting at index ${index}`);
} else {
  console.log('Substring not found');
}

for (let i = 0; i <= n - m; i++) {

advance starting index in big string to check for substring

while (j < m && big[i + j] === sub[j]) {

compare substring letters with big string letters at current position

if (j === m) {

if all substring letters matched, return starting index

Output

hello world

       ↑ substring 'world' found starting at index 6

Complexity Analysis

Time: O(n*m) because in worst case we compare substring at each position in big string

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Naive approach checks all positions and letters; advanced algorithms like KMP improve to O(n) by skipping unnecessary checks

Edge Cases

empty substring

returns 0 because empty substring is found at start by definition

DSA Javascript

for (let i = 0; i <= n - m; i++) {

substring longer than big string

returns -1 immediately because substring cannot fit

DSA Javascript

for (let i = 0; i <= n - m; i++) {

substring not present

returns -1 after checking all positions

DSA Javascript

return -1; // substring not found

When to Use This Pattern

When you need to find if a smaller string appears inside a bigger string, use substring search patterns to check step by step.

Common Mistakes

Mistake: Not stopping comparison when letters mismatch, causing unnecessary checks
Fix: Use a while loop that breaks on first mismatch to avoid extra work

Mistake: Checking beyond the big string length causing errors
Fix: Limit starting index to n - m to avoid out-of-bound checks

Summary

Find if and where a smaller string appears inside a bigger string by checking each position.

Use when you want to locate a word or pattern inside text.

The key is to compare letters one by one and stop early on mismatch.

Practice

1. What does the indexOf method do when used on a string in JavaScript?

easy

A. Converts the string to uppercase

B. Replaces a substring with another string

C. Splits the string into an array of substrings

D. Finds the position of the first occurrence of a substring

Solution

1. Step 1: Understand the purpose of indexOf

   The indexOf method searches a string for a specified substring and returns the position of its first occurrence.

2. Step 2: Confirm behavior on strings

   If the substring is found, it returns the zero-based index; if not found, it returns -1.

3. Final Answer:

   Finds the position of the first occurrence of a substring -> Option D

4. Quick Check:

   indexOf = position of substring [OK]

Hint: Remember: indexOf returns position or -1 if not found [OK]

Common Mistakes:

• Confusing indexOf with replace method
• Thinking indexOf splits the string
• Assuming indexOf changes the string case

2. Which of the following is the correct syntax to check if the substring 'cat' exists in the string text using includes method?

easy

A. text.include('cat')

B. includes(text, 'cat')

C. text.includes('cat')

D. text.contains('cat')

Solution

1. Step 1: Recall the correct method name

   The correct method to check substring presence is includes, called on the string object.

2. Step 2: Verify syntax

   The syntax is string.includes(substring), so text.includes('cat') is correct.

3. Final Answer:

   text.includes('cat') -> Option C

4. Quick Check:

   Correct method call syntax = text.includes('cat') [OK]

Hint: Use string.includes(substring) to check presence [OK]

Common Mistakes:

• Using wrong method name like include or contains
• Calling includes as a standalone function
• Passing arguments in wrong order

3. What will be the output of the following code?

const text = 'hello world';
const pos = text.indexOf('o');
console.log(pos);

medium

A. 4

B. 5

C. -1

D. 6

Solution

1. Step 1: Identify the string and substring

   The string is 'hello world' and the substring searched is 'o'.

2. Step 2: Find the first occurrence of 'o'

   Counting from zero: h(0) e(1) l(2) l(3) o(4) (space 5) w(6) o(7). The first 'o' is at index 4.

3. Step 3: Verify the output

   The code uses indexOf('o') which returns the first occurrence index, which is 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   First 'o' index = 4 [OK]

Hint: Count string index from zero to find first substring position [OK]

Common Mistakes:

• Counting index starting from 1 instead of 0
• Confusing second 'o' position with first
• Assuming indexOf returns -1 if substring exists

4. The following code is intended to check if the substring 'test' exists in str. What is the error?

const str = 'this is a test';
if (str.indexOf == 'test') {
  console.log('Found');
} else {
  console.log('Not Found');
}

medium

A. The variable str is not declared properly

B. indexOf is used without parentheses, so it compares function to string

C. The if condition should use === instead of ==

D. The substring 'test' is misspelled

Solution

1. Step 1: Analyze the use of indexOf

   The code uses str.indexOf without parentheses, so it refers to the function itself, not the result of calling it.

2. Step 2: Understand the comparison

   Comparing a function to a string ('test') is always false, so the condition is incorrect.

3. Final Answer:

   indexOf is used without parentheses, so it compares function to string -> Option B

4. Quick Check:

   Missing parentheses on indexOf causes error [OK]

Hint: Always call indexOf with parentheses and substring argument [OK]

Common Mistakes:

• Forgetting parentheses on indexOf
• Using wrong comparison operator
• Assuming indexOf returns boolean directly

5. You want to find all starting positions of the substring 'ana' in the string 'banana'. Which approach correctly finds all positions?

hard

A. Use a loop with indexOf and update the start position after each find

B. Use includes repeatedly until it returns false

C. Use lastIndexOf to find all positions from the end

D. Use replace to remove substring and count occurrences

Solution

1. Step 1: Understand the problem of multiple occurrences

   To find all positions, you must repeatedly search starting after the last found position.

2. Step 2: Use a loop with indexOf and update start

   Use indexOf('ana', start) in a loop, updating start to position + 1 each time until no more found.

3. Final Answer:

   Use a loop with indexOf and update the start position after each find -> Option A

4. Quick Check:

   Loop + indexOf with updated start = all positions [OK]

Hint: Loop with indexOf(start) to find all substring positions [OK]

Common Mistakes:

• Using includes which returns only true/false
• Using lastIndexOf which finds only last occurrence
• Using replace which changes string and loses positions