Substring Search Patterns in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Substring Search

What is the output of the following TypeScript code that performs a naive substring search?

DSA Typescript

function naiveSearch(text: string, pattern: string): number[] {
  const result: number[] = [];
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j = 0;
    while (j < pattern.length && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) {
      result.push(i);
    }
  }
  return result;
}

const text = "abracadabra";
const pattern = "abra";
console.log(naiveSearch(text, pattern));

A [0, 7]

B [0, 3, 7]

C [3, 7]

D [7]

💡 Hint

Check where the pattern "abra" appears exactly in the text "abracadabra".

The pattern "abra" appears at index 0 and index 7 in the text. The naive search checks each position and finds matches only at these two indices.

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output of the prefix table (also called lps array) constructed by the following TypeScript function for the pattern "ababc"?

DSA Typescript

function buildPrefixTable(pattern: string): number[] {
  const lps: number[] = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else {
      if (length !== 0) {
        length = lps[length - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

console.log(buildPrefixTable("ababc"));

A [0, 1, 2, 0, 1]

B [0, 1, 0, 1, 0]

C [0, 0, 0, 1, 2]

D [0, 0, 1, 2, 0]

💡 Hint

The prefix table stores the length of the longest proper prefix which is also a suffix for each substring.

For "ababc", the prefix table is [0, 0, 1, 2, 0]. This means at index 2, the longest prefix-suffix length is 1, at index 3 it is 2, and so on.

🧠 Conceptual

advanced

Time Complexity of Rabin-Karp Algorithm

What is the worst-case time complexity of the Rabin-Karp substring search algorithm when searching for a pattern of length m in a text of length n?

A O(n + m)

B O(n * m)

C O(m * log n)

D O(n * log m)

💡 Hint

Consider the case when hash collisions happen for every substring.

In the worst case, Rabin-Karp compares the pattern with every substring of the text due to hash collisions, resulting in O(n * m) time.

🔧 Debug

advanced

Identify the Bug in KMP Search Implementation

Given the following TypeScript code for KMP substring search, which option correctly identifies the bug causing incorrect search results?

DSA Typescript

function kmpSearch(text: string, pattern: string): number[] {
  const lps = buildPrefixTable(pattern);
  const result: number[] = [];
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
    }
    if (j === pattern.length) {
      result.push(i - j);
      j = 0; // Bug here
    } else if (i < text.length && text[i] !== pattern[j]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
  return result;
}

function buildPrefixTable(pattern: string): number[] {
  const lps: number[] = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else {
      if (length !== 0) {
        length = lps[length - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

console.log(kmpSearch("ababcababc", "ababc"));

A Not resetting i after a match causes infinite loop.

B The prefix table is built incorrectly causing wrong jumps.

C Resetting j to 0 after a match instead of lps[j-1] causes missed overlapping matches.

D Incrementing i inside the mismatch condition causes skipping characters.

💡 Hint

Check how j is updated after finding a match to allow overlapping matches.

After a match, j should be set to lps[j-1] to allow searching for overlapping patterns. Resetting j to 0 misses these.

🚀 Application

expert

Finding All Anagram Indices Using Sliding Window

You want to find all start indices of substrings in a text that are anagrams of a given pattern. Which approach below correctly implements this using a sliding window technique in TypeScript?

A Use two frequency arrays for pattern and current window; slide window and compare arrays at each step.

B Sort each substring of length pattern.length and compare with sorted pattern at each step.

C Use KMP algorithm directly on the text with the pattern to find anagrams.

D Use Rabin-Karp with a hash of the pattern and compare hashes for each substring without frequency checks.

💡 Hint

Anagrams have the same character counts, so frequency comparison is key.

Sliding window with frequency arrays allows O(n) time complexity by updating counts incrementally and comparing efficiently.

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