Substring Search Patterns in DSA Typescript - Execution Trace

Concept Flow - Substring Search Patterns

Start

↓

Set index i=0 in text

↓

Compare substring with text at i

↓

Match?

|Yes↓

Return i (match found)

↓

End

No↓

Increment i

↓

i <= text.length - substring.length?

|Yes↓

Return -1 (no match)

↓

End

↩Back to Compare

The search moves through the text, checking if the substring matches at each position until a match is found or the text ends.

Execution Sample

DSA Typescript

function substringSearch(text: string, pattern: string): number {
  for (let i = 0; i <= text.length - pattern.length; i++) {
    if (text.slice(i, i + pattern.length) === pattern) {
      return i;
    }
  }
  return -1;
}

This code searches for the first occurrence of 'pattern' in 'text' and returns its starting index or -1 if not found.

Execution Table

Step	Operation	Index i	Substring Compared	Match?	Action	Result
1	Initialize i	0	text[0..2] = 'abc'	No	Increment i	Continue searching
2	Compare at i=1	1	text[1..3] = 'bcd'	No	Increment i	Continue searching
3	Compare at i=2	2	text[2..4] = 'cde'	No	Increment i	Continue searching
4	Compare at i=3	3	text[3..5] = 'def'	Yes	Return i	Match found at index 3
5	End	-	-	-	-	Search stops

💡 At step 4, substring matches text slice, so function returns index 3 and stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	-	0	1	2	3	3
Match Found	false	false	false	false	true	true
Return Value	undefined	undefined	undefined	undefined	3	3

Key Moments - 3 Insights

Why do we stop the loop at i <= text.length - pattern.length?

Because checking beyond that would cause substring to go past text end, which is invalid. See execution_table rows where i stops at 3 for text length 6 and pattern length 3.

What happens if the substring is not found in the text?

The loop finishes without returning, then the function returns -1 as shown by the exit_note and final return in the code.

Why do we compare text.slice(i, i + pattern.length) instead of single characters?

Because substring match requires checking the whole pattern length at once, not just one character. This is shown in execution_table where substring compared is a slice of length equal to pattern.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' when the substring matches?

A 0

B 3

C 2

D 5

💡 Hint

Check the 'Index i' and 'Match?' columns in execution_table row 4.

At which step does the search stop because the substring is found?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Action' and 'Result' columns in execution_table to find when 'Return i' happens.

If the pattern length was 2 instead of 3, how would the maximum value of 'i' change?

A It would increase by 1

B It would decrease by 1

C It would stay the same

D It would double

💡 Hint

Recall the loop condition i <= text.length - pattern.length and check variable_tracker for pattern length effect.

Concept Snapshot

Substring Search Patterns:
- Loop i from 0 to text.length - pattern.length
- At each i, compare text slice with pattern
- If match, return i
- If no match found, return -1
- Stops early when match found

Full Transcript

This visualization shows how substring search works by moving an index through the text and comparing slices to the pattern. The loop runs until the substring matches or the text ends. Variables like index i and match status update each step. The search stops immediately when a match is found, returning the start index. If no match is found, the function returns -1. Key points include why the loop stops early to avoid invalid slices and why full substring slices are compared instead of single characters.

Practice

1. What is the main goal of substring search algorithms in strings?

easy

A. To sort all characters in a string alphabetically

B. To find if a smaller string exists inside a larger string

C. To reverse the entire string

D. To count the total number of vowels in a string

Solution

1. Step 1: Understand substring search purpose

   Substring search algorithms check if a smaller string (pattern) appears inside a bigger string (text).

2. Step 2: Compare options with substring search definition

   Only To find if a smaller string exists inside a larger string matches this goal. Sorting, reversing, or counting vowels are different tasks.

3. Final Answer:

   To find if a smaller string exists inside a larger string -> Option B

4. Quick Check:

   Substring search = find smaller string inside larger [OK]

Hint: Substring search means finding a smaller string inside a bigger one [OK]

Common Mistakes:

• Confusing substring search with sorting or reversing strings
• Thinking substring search counts characters
• Mixing substring search with string length calculation

2. Which of the following is the correct TypeScript syntax to check if string text contains substring pattern?

easy

A. text.includes(pattern)

B. text.contains(pattern)

C. text.has(pattern)

D. text.find(pattern)

Solution

1. Step 1: Recall TypeScript string methods

   TypeScript strings have a method called includes to check substring presence.

2. Step 2: Verify method names

   Only includes is valid. contains, has, and find are not string methods in TypeScript.

3. Final Answer:

   text.includes(pattern) -> Option A

4. Quick Check:

   Use includes() to check substring presence [OK]

Hint: Use includes() method to check substring in TypeScript [OK]

Common Mistakes:

• Using non-existent methods like contains() or has()
• Confusing includes() with find() which is for arrays
• Forgetting parentheses after method name

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

const text = "hello world";
const pattern = "wor";
console.log(text.indexOf(pattern));

medium

A. 6

B. -1

C. 3

D. 0

Solution

1. Step 1: Understand indexOf method

   indexOf returns the starting index of the substring if found, else -1.

2. Step 2: Find substring position in text

   In "hello world", substring "wor" starts at index 6 (0-based counting: h=0, e=1, l=2, l=3, o=4, space=5, w=6).

3. Final Answer:

   6 -> Option A

4. Quick Check:

   indexOf("wor") = 6 [OK]

Hint: indexOf returns start index or -1 if not found [OK]

Common Mistakes:

• Counting index starting from 1 instead of 0
• Confusing indexOf with includes (which returns boolean)
• Assuming indexOf returns substring length

4. Identify the error in the following TypeScript code snippet for substring search:

const text = "typescript";
const pattern = "script";
if (text.find(pattern)) {
  console.log("Found");
} else {
  console.log("Not Found");
}

medium

A. Using if statement without parentheses

B. Missing semicolon after console.log statements

C. Pattern variable is not declared

D. Using find() method on string which does not exist

Solution

1. Step 1: Check string methods in TypeScript

   Strings do not have a find() method. The correct method to check substring is includes() or indexOf().

2. Step 2: Verify other code parts

   Semicolons are optional in TypeScript, pattern is declared, and if statement syntax is correct.

3. Final Answer:

   Using find() method on string which does not exist -> Option D

4. Quick Check:

   Strings have includes(), not find() [OK]

Hint: Use includes() or indexOf(), not find() on strings [OK]

Common Mistakes:

• Assuming find() works on strings like arrays
• Thinking semicolons are mandatory causing errors
• Misreading if statement syntax

5. You want to find all starting indices of substring pattern in string text. Which approach correctly finds multiple occurrences in TypeScript?

hard

A. Use text.indexOf(pattern) once and return that single index

B. Use text.includes(pattern) repeatedly without changing index

C. Use a loop with indexOf(pattern, startIndex) updating startIndex after each find

D. Use text.findAll(pattern) method to get all indices

Solution

1. Step 1: Understand multiple substring search

   To find all occurrences, you must repeatedly search starting after the last found index.

2. Step 2: Analyze each option

   Use a loop with indexOf(pattern, startIndex) updating startIndex after each find uses a loop with indexOf and updates start index, which is correct. Use text.includes(pattern) repeatedly without changing index does not update index, so it loops infinitely or finds only once. Use text.indexOf(pattern) once and return that single index finds only one occurrence. Use text.findAll(pattern) method to get all indices uses a non-existent method.

3. Final Answer:

   Use a loop with indexOf(pattern, startIndex) updating startIndex after each find -> Option C

4. Quick Check:

   Loop with indexOf and updated start index finds all [OK]

Hint: Loop with indexOf and update start index to find all [OK]

Common Mistakes:

• Not updating start index causing infinite loops
• Using includes() which returns boolean, not index
• Expecting findAll() method which does not exist