String immutability in Python - Time & Space Complexity

Time Complexity: String immutability

O(n^2)

Understanding Time Complexity

When working with strings in Python, it's important to know how changes affect performance.

We want to see how the time to modify a string grows as the string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello"
new_text = ""
for char in text:
    new_text += char.upper()
print(new_text)

This code creates a new string by changing each character to uppercase and adding it to a new string.

Identify Repeating Operations

• Primary operation: Looping through each character and adding to a new string.
• How many times: Once for each character in the original string.

How Execution Grows With Input

Each time we add a character, Python creates a new string by copying the old one plus the new character.

Input Size (n)	Approx. Operations
10	About 55 copies (1+2+...+10)
100	About 5050 copies
1000	About 500,500 copies

Pattern observation: The work grows much faster than the input size because each addition copies the whole string so far.

Final Time Complexity

Time Complexity: O(n2)

This means the time to build the new string grows roughly with the square of the string length.

Common Mistake

[X] Wrong: "Adding characters to a string inside a loop is fast and scales linearly."

[OK] Correct: Because strings are immutable, each addition makes a new string copying all previous characters, causing much more work as the string grows.

Interview Connect

Understanding string immutability helps you explain why some string operations can be slow and how to write efficient code.

Self-Check

What if we used a list to collect characters and joined them at the end? How would the time complexity change?

Practice

1. What does it mean that strings in Python are immutable?

easy

A. Strings are stored as numbers internally.

B. You can change parts of a string directly.

C. Strings can be resized but not changed.

D. You cannot change a string after it is created.

Solution

1. Step 1: Understand the meaning of immutable

   Immutable means something cannot be changed after it is made.

2. Step 2: Apply this to strings in Python

   Strings cannot be changed once created; you must make a new string to change text.

3. Final Answer:

   You cannot change a string after it is created. -> Option D

4. Quick Check:

   Immutable = cannot change [OK]

Hint: Immutable means no changes allowed after creation [OK]

Common Mistakes:

• Thinking strings can be changed like lists
• Confusing immutability with fixed size
• Believing strings store numbers only

2. Which of the following is the correct way to create a new string by changing the first letter of word = 'hello' to uppercase?

easy

A. word[0] = 'H'

B. word = 'H' + word[1:]

C. word.upper()[0]

D. word.change(0, 'H')

Solution

1. Step 1: Recognize string immutability

   You cannot assign to a string index like word[0] = 'H'.

2. Step 2: Create a new string combining parts

   Use slicing and concatenation: 'H' + word[1:] makes a new string with first letter changed.

3. Final Answer:

   word = 'H' + word[1:] -> Option B

4. Quick Check:

   Use slicing + concat to change string [OK]

Hint: Use slicing and + to build new strings [OK]

Common Mistakes:

• Trying to assign directly to string index
• Using non-existent string methods like change()
• Misusing upper() which returns full uppercase

3. What will be the output of this code?

text = 'cat'
text[0] = 'b'
print(text)

medium

A. TypeError

B. cat

C. bat

D. SyntaxError

Solution

1. Step 1: Identify the operation on string index

   Trying to assign text[0] = 'b' attempts to change a character in the string.

2. Step 2: Recall string immutability rules

   Strings cannot be changed by index assignment; Python raises a TypeError.

3. Final Answer:

   TypeError -> Option A

4. Quick Check:

   Index assignment on string = TypeError [OK]

Hint: Assigning to string index causes TypeError [OK]

Common Mistakes:

• Expecting string to change without error
• Confusing TypeError with SyntaxError
• Thinking print shows changed string

4. The code below tries to replace the first character of word with 'J'. What is wrong and how to fix it?

word = 'python'
word[0] = 'J'
print(word)

medium

A. Strings are immutable; fix by creating a new string: word = 'J' + word[1:]

B. Syntax error; fix by adding parentheses around 'J'

C. Use word.replace(0, 'J') to fix

D. No error; code works fine

Solution

1. Step 1: Identify the error cause

   Assigning to word[0] is invalid because strings cannot be changed by index.

2. Step 2: Fix by creating a new string

   Build a new string with 'J' plus the rest: word = 'J' + word[1:].

3. Final Answer:

   Strings are immutable; fix by creating a new string: word = 'J' + word[1:] -> Option A

4. Quick Check:

   Fix immutability by new string creation [OK]

Hint: Fix by slicing and concatenating new string [OK]

Common Mistakes:

• Trying to assign directly to string index
• Using replace() incorrectly for index change
• Assuming no error occurs

5. Given a string s = 'banana', how can you create a new string where all 'a' characters are replaced by 'o' without modifying s directly?

hard

A. s = s[0] + 'o' + s[2:]

B. s[1] = 'o'

C. s.replace('a', 'o')

D. s.change('a', 'o')

Solution

1. Step 1: Understand string immutability

   You cannot change characters by index; must create a new string.

2. Step 2: Use string method to replace characters

   s.replace('a', 'o') returns a new string with all 'a' replaced by 'o'.

3. Final Answer:

   s.replace('a', 'o') -> Option C

4. Quick Check:

   Use replace() to get new string with changes [OK]

Hint: Use replace() to get new string with changes [OK]

Common Mistakes:

• Trying to assign to string index
• Using non-existent change() method
• Changing only one character manually