String concatenation and repetition in Python - Time & Space Complexity

Time Complexity: String concatenation and repetition

O(n² * m)

Understanding Time Complexity

We want to understand how the time needed to join or repeat strings changes as the strings get longer or the repetition count grows.

How does the work grow when we add more pieces or repeat more times?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def repeat_and_concat(s, n):
    result = ""
    for _ in range(n):
        result += s
    return result

This code repeats a string s n times by adding it to a result string in a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding the string s to result inside the loop.
• How many times: The loop runs n times, each time concatenating strings.

How Execution Grows With Input

Each time we add s to result, the whole result string is copied to make space for the new addition. So the work grows more than just n times.

Input Size (n)	Approx. Operations
10	About 55 times length of s
100	About 5050 times length of s
1000	About 500500 times length of s

Pattern observation: The work grows roughly like the square of n, because each addition copies a longer string.

Final Time Complexity

Time Complexity: O(n² * m) where m is the length of s

This means the time needed grows roughly with the square of the number of repetitions times the length of the string, making it slower as n gets bigger.

Common Mistake

[X] Wrong: "Adding a string n times in a loop is just O(n) because the loop runs n times."

[OK] Correct: Each addition copies the whole growing string, so the work adds up more than just n times. The string gets longer each time, making concatenation slower.

Interview Connect

Understanding how string operations grow helps you write faster code and explain your choices clearly. It shows you think about how your program behaves as data grows.

Self-Check

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

Practice

1. What does the + operator do when used with strings in Python?

easy

A. Joins two strings together into one

B. Repeats the string multiple times

C. Converts the string to uppercase

D. Splits the string into a list

Solution

1. Step 1: Understand the + operator with strings

   In Python, + combines two strings by joining them end to end.

2. Step 2: Compare with other options

   Repeating strings uses *, uppercase uses .upper(), splitting uses .split().

3. Final Answer:

   Joins two strings together into one -> Option A

4. Quick Check:

   String + String = Joined String [OK]

Hint: Remember: + joins strings, * repeats strings [OK]

Common Mistakes:

• Confusing + with * for repetition
• Thinking + changes string case
• Assuming + splits strings

2. Which of the following is the correct syntax to repeat the string 'hi' 3 times in Python?

easy

A. 'hi' + 3

B. 'hi' * 3

C. 3 'hi'

D. 'hi' ** 3

Solution

1. Step 1: Identify the repetition operator

   In Python, * repeats a string when multiplied by an integer.

2. Step 2: Check other options

   'hi' + 3 causes TypeError (can't add string and int). 3 'hi' is SyntaxError (missing * operator). 'hi' ** 3 causes TypeError (** is for exponents, not string repetition).

3. Final Answer:

   'hi' * 3 -> Option B

4. Quick Check:

   String * Number = Repeated String [OK]

Hint: Use * between string and number to repeat [OK]

Common Mistakes:

• Using + instead of * for repetition
• Trying to use ** which is invalid for strings
• Placing number before string without *

3. What is the output of the following code?

result = 'ab' + 'cd' * 2
print(result)

medium

A. abcdabcd

B. ababcd

C. abcdcdcd

D. abcdcd

Solution

1. Step 1: Evaluate the repetition part

   'cd' * 2 repeats 'cd' twice, resulting in 'cdcd'.

2. Step 2: Concatenate strings

   'ab' + 'cdcd' joins to form 'abcdcd'.

3. Final Answer:

   abcdcd -> Option D

4. Quick Check:

   'ab' + ('cd' * 2) = 'abcdcd' [OK]

Hint: Calculate repetition first, then join strings [OK]

Common Mistakes:

• Adding strings before repeating
• Repeating the whole concatenated string
• Miscounting repeated parts

4. Find the error in this code snippet:

text = 'go' * '3'
print(text)

medium

A. TypeError because string cannot be multiplied by string

B. SyntaxError due to missing parentheses

C. NameError because 'text' is undefined

D. No error, prints 'gogogo'

Solution

1. Step 1: Identify the operands of the * operator

   The code tries to multiply a string 'go' by another string '3'.

2. Step 2: Understand Python's type rules for * operator

   Python allows string * integer but not string * string, causing a TypeError.

3. Final Answer:

   TypeError because string cannot be multiplied by string -> Option A

4. Quick Check:

   String * String = TypeError [OK]

Hint: Multiply string only by integer, not by string [OK]

Common Mistakes:

• Using quotes around number for repetition
• Assuming implicit conversion to int
• Ignoring error messages

5. You want to create a string that repeats the word 'yes' 4 times, separated by a dash -. Which code produces 'yes-yes-yes-yes'?

hard

A. 'yes' + '-' * 3

B. 'yes-' * 4

C. ('yes-' * 4)[:-1]

D. '-'.join('yes' * 4)

Solution

1. Step 1: Understand the desired output

   The string should be 'yes-yes-yes-yes' with 3 dashes separating 4 'yes'.

2. Step 2: Analyze each option

   ('yes-' * 4)[:-1] repeats 'yes-' 4 times: 'yes-yes-yes-yes-' then removes last dash with [:-1]. 'yes-' * 4 leaves trailing dash. '-'.join('yes' * 4) joins characters, not words. 'yes' + '-' * 3 adds only one dash.

3. Final Answer:

   ('yes-' * 4)[:-1] -> Option C

4. Quick Check:

   Repeat with dash, then remove last dash [OK]

Hint: Repeat with dash, then remove last dash [OK]

Common Mistakes:

• Leaving extra dash at end
• Joining characters instead of words
• Adding fewer dashes than needed