Common string transformations in Python - Time & Space Complexity

Time Complexity: Common string transformations

O(n)

Understanding Time Complexity

When we change strings by making them uppercase, lowercase, or replacing parts, 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.

text = "Hello World"
upper_text = text.upper()
lower_text = text.lower()
replaced_text = text.replace('o', '0')
trimmed_text = text.strip()
    

This code changes a string to uppercase, lowercase, replaces characters, and removes spaces from the ends.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Going through each character in the string to change or check it.
• How many times: Once for each character in the string for each transformation.

How Execution Grows With Input

As the string gets longer, the time to change it grows in a straight line with the number of characters.

Input Size (n)	Approx. Operations
10	About 10 operations per transformation
100	About 100 operations per transformation
1000	About 1000 operations per transformation

Pattern observation: The work grows evenly as the string length grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to do these string changes grows directly with the string length.

Common Mistake

[X] Wrong: "Changing a string's case or replacing characters is instant and does not depend on string size."

[OK] Correct: Each character must be checked or changed, so longer strings take more time.

Interview Connect

Understanding how string operations grow with size helps you write clear and efficient code, a skill valued in many coding challenges and real projects.

Self-Check

"What if we used a method that only changes the first character of the string? How would the time complexity change?"

Practice

1. Which Python string method converts all characters in a string to uppercase?
text = "hello world"

easy

A. text.upper()

B. text.lower()

C. text.strip()

D. text.replace()

Solution

1. Step 1: Understand the purpose of each method

   upper() converts all letters to uppercase, lower() to lowercase, strip() removes spaces, replace() changes parts of the string.

2. Step 2: Identify the method that changes all letters to uppercase

   upper() is the method that does this.

3. Final Answer:

   text.upper() -> Option A

4. Quick Check:

   upper() = text.upper() [OK]

Hint: Uppercase all letters with upper() method [OK]

Common Mistakes:

• Confusing upper() with lower()
• Using strip() to change case
• Trying replace() without arguments

2. Which of the following is the correct syntax to remove whitespace from both ends of the string text?

easy

A. text.strip()

B. text.trim()

C. text.remove()

D. text.cut()

Solution

1. Step 1: Recall Python string methods for trimming spaces

   Python uses strip() to remove whitespace from both ends of a string.

2. Step 2: Check the options for correct method name

   trim(), remove(), and cut() are not valid Python string methods.

3. Final Answer:

   text.strip() -> Option A

4. Quick Check:

   strip() = text.strip() [OK]

Hint: Use strip() to remove spaces from start and end [OK]

Common Mistakes:

• Using trim() which is not a Python method
• Trying remove() or cut() which don't exist
• Confusing strip() with replace()

3. What is the output of the following code?

text = "apple,banana,cherry"
result = text.split(",")
print(result)

medium

A. apple,banana,cherry

B. ['apple,banana,cherry']

C. apple banana cherry

D. ['apple', 'banana', 'cherry']

Solution

1. Step 1: Understand split() method with comma separator

   split(",") breaks the string at each comma, creating a list of parts.

2. Step 2: Apply split to the string

   Splitting "apple,banana,cherry" by comma gives ['apple', 'banana', 'cherry'].

3. Final Answer:

   ['apple', 'banana', 'cherry'] -> Option D

4. Quick Check:

   split(",") = list of words [OK]

Hint: split(',') breaks string into list by commas [OK]

Common Mistakes:

• Expecting a string instead of list
• Using split() without argument
• Confusing split() with join()

4. The following code is intended to replace all spaces with dashes in the string text. What is the error?

text = "hello world"
text.replace(" ", "-")
print(text)

medium

A. No error, output is 'hello-world'

B. RuntimeError because replace() needs assignment

C. Output is 'hello world' because replace() does not change original string

D. SyntaxError due to wrong replace() usage

Solution

1. Step 1: Understand string immutability in Python

   Strings cannot be changed in place; methods like replace() return a new string.

2. Step 2: Check code behavior

   text.replace(" ", "-") returns new string but original text remains unchanged because result is not assigned.

3. Final Answer:

   Output is 'hello world' because replace() does not change original string -> Option C

4. Quick Check:

   replace() returns new string, assign it [OK]

Hint: Assign replace() result to variable to update string [OK]

Common Mistakes:

• Not assigning replace() result
• Expecting replace() to modify string in place
• Confusing syntax errors with logic errors

5. You have a list of words: words = [' apple', 'Banana ', ' CHERRY ']. Which code correctly creates a new list with all words trimmed and in lowercase?

hard

A. [word.strip() + word.lower() for word in words]

B. [word.strip().lower() for word in words]

C. [word.lower().strip for word in words]

D. [word.lower() for word in words.strip()]

Solution

1. Step 1: Understand the order of strip() and lower()

   strip() removes spaces, lower() converts to lowercase. Order doesn't matter here since they don't interfere.

2. Step 2: Analyze each option

   A concatenates strip() result with lower() result, doubling content. B calls lower() then references .strip without (), yielding method objects. C chains strip().lower() correctly. D calls strip() on list, causing AttributeError.

3. Final Answer:

   [word.strip().lower() for word in words] -> Option B

4. Quick Check:

   List comprehension with strip() and lower() [OK]

Hint: Use list comprehension with strip() then lower() [OK]

Common Mistakes:

• Concatenating strings instead of chaining methods
• Calling strip() on list
• Forgetting parentheses on strip()