String replacement in MATLAB - Time & Space Complexity

Time Complexity: String replacement

O(n*m)

Understanding Time Complexity

We want to understand how the time it takes to replace parts of a string changes as the string gets longer.

How does the work grow when we replace text inside a bigger string?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

originalStr = "hello world hello";
searchStr = "hello";
replaceStr = "hi";
newStr = strrep(originalStr, searchStr, replaceStr);

This code replaces all occurrences of "hello" with "hi" in the given string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the original string to find all matches of the search string.
• How many times: The scan goes through the entire string once, checking each position for a match.

How Execution Grows With Input

As the string gets longer, the function checks more positions to find matches.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 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 replace text grows linearly with the product of the string length and the search string length.

Common Mistake

[X] Wrong: "Replacing text takes the same time no matter how long the string is."

[OK] Correct: The function must check each part of the string, so longer strings take more time.

Interview Connect

Understanding how string operations grow with input size helps you explain your code choices clearly and confidently.

Self-Check

"What if we replaced multiple different substrings at once? How would the time complexity change?"

Practice

1. What does the MATLAB function strrep('hello world', 'world', 'MATLAB') do?

easy

A. Replaces 'world' with 'MATLAB' resulting in 'hello MATLAB'

B. Removes the word 'world' from the string

C. Returns an error because 'world' is not a variable

D. Converts the entire string to uppercase

Solution

1. Step 1: Understand strrep function

   The function strrep replaces all occurrences of a substring with a new substring in a given string.

2. Step 2: Apply strrep to the example

   It replaces 'world' with 'MATLAB' in 'hello world', resulting in 'hello MATLAB'.

3. Final Answer:

   Replaces 'world' with 'MATLAB' resulting in 'hello MATLAB' -> Option A

4. Quick Check:

   strrep('hello world', 'world', 'MATLAB') = 'hello MATLAB' [OK]

Hint: Remember: strrep replaces all matching substrings [OK]

Common Mistakes:

• Thinking strrep removes substrings instead of replacing
• Confusing strrep with uppercase functions
• Assuming strrep only works on variables

2. Which of the following is the correct syntax to replace all occurrences of 'cat' with 'dog' in the string text = 'cat and cat'?

easy

A. replace(text, cat, dog)

B. strrep(text, 'cat', 'dog')

C. text.replace('cat', 'dog')

D. str_replace(text, 'cat', 'dog')

Solution

1. Step 1: Recall MATLAB string replacement syntax

   In MATLAB, the function to replace substrings is strrep(originalStr, oldSubstr, newSubstr).

2. Step 2: Match the correct syntax

   strrep(text, 'cat', 'dog') uses strrep correctly with the right order of arguments.

3. Final Answer:

   strrep(text, 'cat', 'dog') -> Option B

4. Quick Check:

   Correct MATLAB syntax for string replacement is strrep() [OK]

Hint: Use strrep(original, old, new) for replacements [OK]

Common Mistakes:

• Using Python or other language syntax by mistake
• Misspelling function names
• Using dot notation which MATLAB strings don't support

3. What is the output of the following MATLAB code?

str = 'apple banana apple';
newStr = strrep(str, 'apple', 'orange');
disp(newStr);

medium

A. orange banana apple

B. apple banana orange

C. orange banana orange

D. apple banana apple

Solution

1. Step 1: Identify the original string and replacement

   The original string is 'apple banana apple'. The function replaces all 'apple' with 'orange'.

2. Step 2: Apply strrep to replace all occurrences

   Both 'apple' words are replaced, resulting in 'orange banana orange'.

3. Final Answer:

   orange banana orange -> Option C

4. Quick Check:

   strrep replaces all matches, not just first [OK]

Hint: strrep replaces every match, not just one [OK]

Common Mistakes:

• Replacing only the first occurrence
• Confusing strrep with regex functions
• Expecting original string unchanged

4. The following MATLAB code is intended to replace 'dog' with 'cat' in the string text = 'dog and dog'. What is the error?

text = 'dog and dog';
newText = strrep(text, dog, cat);
disp(newText);

medium

A. Missing quotes around 'dog' and 'cat' causing an error

B. strrep cannot replace substrings in character arrays

C. disp cannot display strings

D. No error, code runs correctly

Solution

1. Step 1: Check argument types in strrep

   In MATLAB, substrings must be given as strings or character arrays enclosed in quotes.

2. Step 2: Identify missing quotes causing error

   The code uses dog and cat without quotes, which MATLAB treats as variables, causing an error.

3. Final Answer:

   Missing quotes around 'dog' and 'cat' causing an error -> Option A

4. Quick Check:

   String literals need quotes in strrep arguments [OK]

Hint: Always quote substrings in strrep arguments [OK]

Common Mistakes:

• Forgetting quotes around substrings
• Assuming variables are strings automatically
• Thinking disp cannot show strings

5. Given a string array words = ["red", "blue", "red", "green"], which MATLAB code replaces all occurrences of "red" with "yellow" correctly?

hard

A. newWords = strrep(words, red, 'yellow');

B. newWords = strrep(words, "red", yellow);

C. newWords = strrep(words, red, yellow);

D. newWords = replace(words, 'red', 'yellow');

Solution

1. Step 1: Understand string array replacement functions

   For string arrays, MATLAB's replace function works correctly, while strrep works on character arrays.

2. Step 2: Identify the correct function and syntax

   newWords = replace(words, 'red', 'yellow'); uses replace with proper quotes, which replaces all "red" with "yellow" in the string array.

3. Final Answer:

   newWords = replace(words, 'red', 'yellow'); -> Option D

4. Quick Check:

   Use replace() for string arrays, strrep() for char arrays [OK]

Hint: Use replace() for string arrays, strrep() for char arrays [OK]

Common Mistakes:

• Using strrep on string arrays (causes error)
• Forgetting quotes around substrings
• Confusing variable names with strings