String searching and extraction in C Sharp (C#) - Time & Space Complexity

Time Complexity: String searching and extraction

O(n * m)

Understanding Time Complexity

When we search or extract parts of a string, the time it takes depends on the string's length.

We want to know how the work grows as the string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string text = "Hello, welcome to the world of C# programming.";
string wordToFind = "world";

int index = text.IndexOf(wordToFind);
if (index != -1)
{
    string extracted = text.Substring(index, wordToFind.Length);
    Console.WriteLine(extracted);
}

This code searches for a word inside a string and extracts it if found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The search method IndexOf scans the string to find the word.
• How many times: It checks characters one by one until it finds the word or reaches the end.

How Execution Grows With Input

As the string gets longer, the search checks more characters.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The work grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to search grows linearly with the string length and the word length.

Common Mistake

[X] Wrong: "Searching a string is always instant, no matter how long it is."

[OK] Correct: The program must check characters one by one, so longer strings take more time.

Interview Connect

Understanding how string search time grows helps you explain efficiency clearly and shows you know how programs handle text.

Self-Check

"What if we searched for multiple words one after another? How would the time complexity change?"

Practice

1. What does the IndexOf method return if the searched substring is not found in a string?

easy

A. 0

B. -1

C. null

D. An exception is thrown

Solution

1. Step 1: Understand IndexOf behavior

   The IndexOf method returns the zero-based index of the first occurrence of the substring if found.

2. Step 2: Check return value when substring is missing

   If the substring is not found, IndexOf returns -1 to indicate absence.

3. Final Answer:

   -1 -> Option B

4. Quick Check:

   IndexOf returns -1 if substring missing [OK]

Hint: Remember: Not found means -1 from IndexOf [OK]

Common Mistakes:

• Thinking it returns 0 when not found
• Expecting null instead of -1
• Assuming it throws an error if missing

2. Which of the following is the correct syntax to extract a substring starting at index 3 with length 5 from a string text?

easy

A. text.Substring(3, 5);

B. text.SubString(5, 3);

C. text.Substring(5);

D. text.Substr(3, 5);

Solution

1. Step 1: Recall Substring method signature

   Substring takes start index first, then length: Substring(int startIndex, int length).

2. Step 2: Match correct syntax

   text.Substring(3, 5); uses correct method name and parameter order: start at 3, length 5.

3. Final Answer:

   text.Substring(3, 5); -> Option A

4. Quick Check:

   Correct method and parameters = text.Substring(3, 5); [OK]

Hint: Remember: Substring(startIndex, length) with capital S [OK]

Common Mistakes:

• Using wrong method name like Substr or SubString
• Swapping start index and length parameters
• Using only one parameter when two are needed

3. What is the output of this code?

string s = "hello world";
int pos = s.IndexOf("world");
string part = s.Substring(pos, 5);
Console.WriteLine(part);

medium

A. hello

B. worldd

C. world

D. error

Solution

1. Step 1: Find index of "world" in string

   "world" starts at index 6 in "hello world".

2. Step 2: Extract substring from index 6 with length 5

   Substring(6, 5) extracts "world" exactly.

3. Final Answer:

   world -> Option C

4. Quick Check:

   IndexOf + Substring extracts "world" [OK]

Hint: IndexOf finds start, Substring extracts exact length [OK]

Common Mistakes:

• Using wrong start index for Substring
• Confusing length parameter
• Expecting output to include extra characters

4. The following code throws an exception. What is the main cause?

string s = "example";
int pos = s.IndexOf("z");
string part = s.Substring(pos, 3);
Console.WriteLine(part);

medium

A. Substring called with negative start index

B. IndexOf throws exception if not found

C. Length parameter is too large

D. Console.WriteLine cannot print substrings

Solution

1. Step 1: Check IndexOf result for "z"

   "z" is not in "example", so IndexOf returns -1.

2. Step 2: Substring called with start index -1 causes exception

   Substring cannot start at negative index, so it throws ArgumentOutOfRangeException.

3. Final Answer:

   Substring called with negative start index -> Option A

4. Quick Check:

   Negative index in Substring causes error [OK]

Hint: Check if IndexOf is -1 before using Substring [OK]

Common Mistakes:

• Assuming IndexOf throws exception when not found
• Ignoring negative index causes Substring error
• Blaming Console.WriteLine for error

5. You want to extract the first word from a sentence stored in string sentence. Which code correctly extracts the first word assuming words are separated by spaces?

hard

A. string firstWord = sentence.Substring(sentence.IndexOf(' ') + 1);

B. string firstWord = sentence.Substring(0, sentence.IndexOf(' '));

C. int spacePos = sentence.IndexOf(' ');
string firstWord = sentence.Substring(spacePos);

D. int spacePos = sentence.IndexOf(' ');
string firstWord = spacePos == -1 ? sentence : sentence.Substring(0, spacePos);

Solution

1. Step 1: Find position of first space

   Use IndexOf(' ') to find where the first space is.

2. Step 2: Extract substring from start to space or whole string if no space

   If no space found (-1), the whole sentence is one word; else extract from 0 to space position.

3. Final Answer:

   int spacePos = sentence.IndexOf(' '); string firstWord = spacePos == -1 ? sentence : sentence.Substring(0, spacePos); -> Option D

4. Quick Check:

   Check for space, then substring from start [OK]

Hint: Check if space exists before substring to avoid errors [OK]

Common Mistakes:

• Not handling case when no space exists
• Extracting substring after space instead of before
• Using wrong substring parameters