Searching and replacing text in Python - Time & Space Complexity

Time Complexity: Searching and replacing text

O(n)

Understanding Time Complexity

When we search and replace text in a string, we want to know how the time it takes changes as the text gets longer.

We ask: How does the work grow when the input text grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello world hello"
old = "hello"
new = "hi"

result = text.replace(old, new)
print(result)

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each part of the text to find matches of the old word.
• How many times: The operation runs once for each character in the text string.

How Execution Grows With Input

As the text gets longer, the program checks more characters 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 directly with the length of the text.

Final Time Complexity

Time Complexity: O(n)

This means the time to replace text grows in a straight line as the text gets longer.

Common Mistake

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

[OK] Correct: The program must look through the whole text to find what to replace, so longer text means more work.

Interview Connect

Understanding how searching and replacing text scales helps you explain how programs handle big inputs smoothly.

Self-Check

"What if we replaced only the first occurrence instead of all? How would the time complexity change?"

Practice

1. What does the replace method do in Python strings?

easy

A. It finds a specified substring and replaces it with another substring.

B. It deletes a substring from the string permanently.

C. It changes the original string directly without creating a new one.

D. It counts how many times a substring appears in the string.

Solution

1. Step 1: Understand the purpose of replace()

   The replace method searches for a substring and replaces it with another substring.

2. Step 2: Check if it modifies original string

   Strings are immutable in Python, so replace returns a new string without changing the original.

3. Final Answer:

   It finds a specified substring and replaces it with another substring. -> Option A

4. Quick Check:

   replace() = find and change substring [OK]

Hint: Remember: replace returns new string, original stays same [OK]

Common Mistakes:

• Thinking replace changes the original string
• Confusing replace with delete or count methods
• Assuming replace modifies in-place

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

easy

A. text.replace('cat', 'dog', all=True)

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

C. text.replace('cat' -> 'dog')

D. text.replace('cat', 'dog', count=0)

Solution

1. Step 1: Recall replace() syntax

   The correct syntax is string.replace(old, new[, count]), where old and new are strings.

2. Step 2: Analyze options

   text.replace('cat', 'dog') matches the correct syntax. Options A, B, and D use invalid syntax or parameters.

3. Final Answer:

   text.replace('cat', 'dog') -> Option B

4. Quick Check:

   replace(old, new) syntax = text.replace('cat', 'dog') [OK]

Hint: Use replace(old, new) without extra keywords [OK]

Common Mistakes:

• Using arrows or keywords inside replace()
• Adding unsupported parameters like all=True
• Confusing parameter order

3. What will be the output of this code?

text = 'apple apple apple'
new_text = text.replace('apple', 'orange', 2)
print(new_text)

medium

A. 'apple orange orange'

B. 'orange orange orange'

C. 'orange orange apple'

D. 'apple apple orange'

Solution

1. Step 1: Understand replace with count

   The third argument 2 limits replacements to first two occurrences.

2. Step 2: Apply replacements

   First two 'apple' become 'orange', last remains 'apple'. Result: 'orange orange apple'.

3. Final Answer:

   'orange orange apple' -> Option C

4. Quick Check:

   replace with count=2 changes first two only [OK]

Hint: Count limits how many replacements happen [OK]

Common Mistakes:

• Replacing all occurrences ignoring count
• Replacing from the end instead of start
• Miscounting number of replacements

4. The following code tries to replace 'blue' with 'red' but causes an error. What is the error?

text = 'blue sky'
text.replace('blue', 'red', 'all')
print(text)

medium

A. SyntaxError due to wrong quotes

B. AttributeError because replace is not a string method

C. No error, prints 'red sky'

D. TypeError because 'all' is not an integer for count

Solution

1. Step 1: Check replace() parameters

   The third parameter must be an integer count, but 'all' is a string.

2. Step 2: Identify error type

   Passing a string instead of int causes a TypeError at runtime.

3. Final Answer:

   TypeError because 'all' is not an integer for count -> Option D

4. Quick Check:

   replace count must be int, not string [OK]

Hint: Count parameter must be integer, not string [OK]

Common Mistakes:

• Using strings instead of integers for count
• Expecting replace to modify original string
• Confusing error types

5. You have a paragraph stored in text. You want to replace only the first 3 occurrences of the word 'error' with 'issue'. Which code snippet correctly does this?

hard

A. new_text = text.replace('error', 'issue', 3)

B. new_text = text.replace('error', 'issue', count=3)

C. new_text = text.replace('error', 'issue', '3')

D. new_text = text.replace('error', 'issue')[:3]

Solution

1. Step 1: Use replace with count parameter

   To replace only first 3 occurrences, use replace(old, new, count) with count=3.

2. Step 2: Analyze options

   new_text = text.replace('error', 'issue', 3) uses correct syntax. new_text = text.replace('error', 'issue', count=3) uses invalid keyword argument. new_text = text.replace('error', 'issue', '3') passes count as string. new_text = text.replace('error', 'issue')[:3] slices string incorrectly.

3. Final Answer:

   new_text = text.replace('error', 'issue', 3) -> Option A

4. Quick Check:

   replace(old, new, 3) replaces first 3 only [OK]

Hint: Use third argument as integer count for limited replacements [OK]

Common Mistakes:

• Using keyword count instead of positional argument
• Passing count as string instead of int
• Trying to slice string after replace