Substring extraction in PHP - Time & Space Complexity

Time Complexity: Substring extraction

O(k)

Understanding Time Complexity

When we extract a part of a string, it is important to know how the time needed grows as the string gets longer.

We want to find out how the work changes when the input string size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "Hello, world!";
$start = 7;
$length = 5;
$substring = substr($string, $start, $length);
echo $substring;
    

This code takes a string and extracts a smaller part starting at a certain position with a given length.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying characters from the original string to create the substring.
• How many times: The number of characters copied equals the length of the substring requested.

How Execution Grows With Input

As the substring length grows, the work grows proportionally because each character must be copied.

Input Size (substring length)	Approx. Operations
10	About 10 character copies
100	About 100 character copies
1000	About 1000 character copies

Pattern observation: The time grows linearly with the length of the substring extracted.

Final Time Complexity

Time Complexity: O(k)

This means the time needed grows directly with the length of the substring you want to extract.

Common Mistake

[X] Wrong: "Extracting a substring always takes the same time no matter how long it is."

[OK] Correct: Actually, the function must copy each character one by one, so longer substrings take more time.

Interview Connect

Understanding how substring extraction scales helps you reason about string operations in real projects and interviews.

Self-Check

"What if we extract a substring without specifying length, how would the time complexity change?"

Practice

1. What does the PHP function substr($text, 2, 3) do?

easy

A. Extracts the first 3 characters of $text

B. Extracts 2 characters from $text starting at index 3

C. Extracts 3 characters from $text starting at index 2

D. Extracts the last 3 characters of $text

Solution

1. Step 1: Understand substr parameters

   The first parameter is the string, the second is the start index (0-based), and the third is the length of substring.

2. Step 2: Apply to given function

   Starting at index 2 means the third character, and length 3 means extract 3 characters from there.

3. Final Answer:

   Extracts 3 characters from $text starting at index 2 -> Option C

4. Quick Check:

   substr(string, 2, 3) = 3 chars from index 2 [OK]

Hint: Remember start is zero-based, length is how many chars [OK]

Common Mistakes:

• Confusing start index with length
• Thinking start counts from 1 instead of 0
• Assuming length is mandatory

2. Which of the following is the correct syntax to extract a substring from a string $str starting at position 4 with length 5 in PHP?

easy

A. substr($str, 5);

B. substr($str, 4, 5);

C. substr($str, 4);

D. substr($str, 5, 4);

Solution

1. Step 1: Recall substr syntax

   substr(string, start, length) extracts substring starting at 'start' index with 'length' characters.

2. Step 2: Match parameters to question

   Start is 4, length is 5, so substr($str, 4, 5) is correct syntax.

3. Final Answer:

   substr($str, 4, 5); -> Option B

4. Quick Check:

   substr($str, 4, 5) = correct syntax [OK]

Hint: Syntax is substr(string, start, length) with start zero-based [OK]

Common Mistakes:

• Swapping start and length values
• Omitting length when needed
• Using 1-based start index

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

$text = "Hello World!";
echo substr($text, 6, 5);

medium

A. World

B. World!

C. Hello

D. orld!

Solution

1. Step 1: Identify substring start and length

   Start index is 6 (0-based), length is 5 characters.

2. Step 2: Extract substring from "Hello World!"

   Index 6 is 'W', next 5 chars are 'World'.

3. Final Answer:

   World -> Option A

4. Quick Check:

   substr("Hello World!", 6, 5) = "World" [OK]

Hint: Count characters from zero, then take length chars [OK]

Common Mistakes:

• Including the exclamation mark mistakenly
• Starting count from 1 instead of 0
• Confusing length with end index

4. The following PHP code is intended to extract the substring "cat" from the string "concatenate". What is wrong?

$word = "concatenate";
echo substr($word, 3, 4);

medium

A. The length parameter is too long; it should be 3

B. The start index should be 4 instead of 3

C. The substr function cannot extract "cat" from this string

D. There is no error; the code works correctly

Solution

1. Step 1: Locate substring "cat" in "concatenate"

   "cat" starts at index 3: c(3), a(4), t(5).

2. Step 2: Check length parameter

   Length 4 extracts "cate" (4 chars), but "cat" is only 3 chars, so length should be 3.

3. Final Answer:

   The length parameter is too long; it should be 3 -> Option A

4. Quick Check:

   substr("concatenate", 3, 3) = "cat" [OK]

Hint: Count exact substring length to avoid extra chars [OK]

Common Mistakes:

• Using wrong start index
• Assuming substr auto-trims extra chars
• Thinking substr can't extract middle parts

5. You have a string $data = "user:john;id:12345;role:admin";. How do you extract the user name "john" using substr and strpos functions in PHP?

hard

A. substr($data, 0, strpos($data, ':'));

B. substr($data, 5, 4);

C. substr($data, strpos($data, ';') + 1, 4);

D. substr($data, strpos($data, ':') + 1, strpos($data, ';') - strpos($data, ':') - 1);

Solution

1. Step 1: Find start position of username

   Use strpos($data, ':') to find colon after "user", add 1 to start after colon.

2. Step 2: Find length of username substring

   Find position of first semicolon with strpos($data, ';'), subtract start position and 1 to get length.

3. Step 3: Use substr with calculated start and length

   substr($data, start, length) extracts "john" correctly.

4. Final Answer:

   substr($data, strpos($data, ':') + 1, strpos($data, ';') - strpos($data, ':') - 1); -> Option D

5. Quick Check:

   Use strpos to find delimiters, substr extracts between them [OK]

Hint: Use strpos to find delimiters, substr extracts between them [OK]

Common Mistakes:

• Hardcoding start and length without dynamic positions
• Using wrong delimiter positions
• Extracting wrong substring part