Substring Search Patterns in DSA C# - Time & Space Complexity

Time Complexity: Substring Search Patterns

O(n * m)

Understanding Time Complexity

When searching for a smaller string inside a bigger one, it is important to know how long it takes as the strings grow.

We want to understand how the search time changes when the text or pattern gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Naive substring search
public static int NaiveSearch(string text, string pattern) {
    int n = text.Length;
    int m = pattern.Length;
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j])
                break;
        }
        if (j == m) return i; // pattern found
    }
    return -1; // not found
}
    

This code tries to find the first place where the pattern appears in the text by checking each position one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two nested loops: outer loop moves through text positions, inner loop compares characters of pattern.
• How many times: Outer loop runs about (n - m + 1) times, inner loop runs up to m times for each outer iteration.

How Execution Grows With Input

As the text and pattern get longer, the number of character comparisons grows quickly.

Input Size (n)	Approx. Operations
10 (text), 3 (pattern)	Up to 24 comparisons
100 (text), 10 (pattern)	Up to 910 comparisons
1000 (text), 50 (pattern)	Up to 47,550 comparisons

Pattern observation: The work grows roughly by multiplying text length by pattern length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to search grows proportionally to the size of the text times the size of the pattern.

Common Mistake

[X] Wrong: "The search always takes time proportional to the text length only."

[OK] Correct: Because for each position in the text, we may need to check every character of the pattern, so pattern length matters too.

Interview Connect

Understanding how substring search time grows helps you explain and improve search algorithms in real projects.

Self-Check

"What if we used a more advanced algorithm like KMP? How would the time complexity change?"

Practice

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

easy

A. To sort characters in a string alphabetically

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

C. To reverse the order of characters in a string

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

Solution

1. Step 1: Understand substring search goal

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

2. Step 2: Compare with other options

   Sorting, reversing, and counting characters are different string operations unrelated to substring search.

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 bigger string [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
• Assuming substring search changes the string

2. Which of the following is the correct way to check if string text contains substring pattern in C#?

easy

A. bool found = Contains(text, pattern);

B. bool found = text.Find(pattern);

C. bool found = text.Contains(pattern);

D. bool found = text.Index(pattern);

Solution

1. Step 1: Recall C# string method for substring check

   The correct method to check if a string contains another is Contains, called on the string instance.

2. Step 2: Validate method usage

   text.Contains(pattern) returns a boolean indicating if pattern is inside text. Other options are invalid or do not exist.

3. Final Answer:

   bool found = text.Contains(pattern); -> Option C

4. Quick Check:

   Use Contains method on string to check substring [OK]

Hint: Use text.Contains(pattern) to check substring presence [OK]

Common Mistakes:

• Using non-existent methods like Find or Index
• Calling Contains as a standalone function
• Confusing method names or parameters

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

string text = "hello world";
string pattern = "wor";
bool result = text.Contains(pattern);
Console.WriteLine(result);

medium

A. True

B. Runtime exception

C. Compilation error

D. False

Solution

1. Step 1: Check if pattern "wor" is in text "hello world"

   The substring "wor" appears starting at index 6 in "hello world".

2. Step 2: Evaluate Contains method result

   Since the substring exists, text.Contains(pattern) returns true, so result is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Substring "wor" in "hello world" = true [OK]

Hint: Check if substring is inside text literally to get true/false [OK]

Common Mistakes:

• Assuming Contains returns index instead of bool
• Thinking substring is not present due to partial match
• Confusing output with string printing

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

string text = "data structures";
string pattern = "struct";
int index = text.IndexOf(pattern);
if (index)
{
    Console.WriteLine("Found at " + index);
}

medium

A. The if condition should check if index >= 0

B. IndexOf method does not exist for strings

C. Pattern variable is not declared

D. Console.WriteLine syntax is incorrect

Solution

1. Step 1: Understand IndexOf return value

   IndexOf returns the starting index of the substring or -1 if not found.

2. Step 2: Check if condition usage

   The if condition if (index) is invalid because index is an int, not a boolean. It should check index >= 0 to confirm substring found.

3. Final Answer:

   The if condition should check if index >= 0 -> Option A

4. Quick Check:

   Check index >= 0 to confirm substring found [OK]

Hint: Check if index >= 0 to confirm substring found [OK]

Common Mistakes:

• Using int directly as boolean in if condition
• Assuming IndexOf returns boolean
• Ignoring negative index meaning not found

5. Given a list of strings words and a pattern string p, which approach best finds all words containing p as a substring efficiently in C#?

hard

A. Use words.IndexOf(p) directly

B. Sort the list and use binary search for the pattern

C. Replace all occurrences of p in each word with empty string

D. Use a loop to check each word with word.Contains(p) and collect matches

Solution

1. Step 1: Understand substring search in multiple strings

   To find all words containing p, we must check each word individually for the substring.

2. Step 2: Evaluate options for efficiency and correctness

   Using a loop with word.Contains(p) is straightforward and efficient. Sorting and binary search do not help substring search. words.IndexOf(p) is invalid because words is a list of strings, not a string. Replacing substrings does not find matches.

3. Final Answer:

   Use a loop to check each word with word.Contains(p) and collect matches -> Option D

4. Quick Check:

   Loop + Contains per word finds all substring matches [OK]

Hint: Loop through words and use Contains to find substring matches [OK]

Common Mistakes:

• Trying binary search for substring matching
• Using IndexOf on list instead of strings
• Replacing substrings instead of checking presence