---

📘 String Concatenation

String Concatenation means joining two or more strings end-to-end to form a new string.

Example:

"Hello" + "World" = "HelloWorld"

In Data Structures, string concatenation is important because:

• Strings are sequences (like arrays).
• Concatenation involves copying characters.
• Performance depends on the immutability of strings.

---

📌 Strings as Data Structure

A string is essentially:

👉 A sequence of characters stored in contiguous memory, similar to an array.

In many languages (including Python), strings are:

• Immutable
• Fixed-size once created
• Any modification creates a new string object

This affects performance of concatenation.

---

📌 String Concatenation – Time Complexity

Since strings are immutable, concatenating strings like:

s = s + "a"

creates a new string each time.

Time Complexity:

[
O(n)
]
Where n = length of resulting string.

If you repeat this in a loop, total cost becomes:
[
O(n^2)
]
This is important in competitive programming and algorithm design.

---

📘 String Concatenation in Python

Python provides multiple ways:

---

1. Using + Operator

s = "Hello"
s = s + "World"
print(s)  # HelloWorld

✔ Easy to read

✘ Costly for repeated concatenation

Time complexity each time = O(n)

---

2. Using += Operator

s = ""
for i in range(5):
    s += "a"
print(s)  # aaaaa

Internally same as s = s + "a"
👉 Still O(n) per concatenation → O(n²) for loops.

---

3. Using join() (Best Way)

Recommended for joining multiple strings efficiently.

words = ["data", "structure", "python"]
result = "".join(words)
print(result)  # datastructurepython

✔ Very fast

✔ O(n) total

✔ Used in production code

✔ No repeated copying

Internally uses an optimized single-pass allocation.

---

4. Using StringIO (for heavy concatenation)

When continuously building large strings:

from io import StringIO

buffer = StringIO()
buffer.write("Hello")
buffer.write("World")
result = buffer.getvalue()
print(result)  # HelloWorld

✔ Efficient for huge outputs

✔ Avoids repeated copying

✔ Useful in competitive coding

---

5. Using f-Strings / format()

Not ideal for loops, but good for small operations:

name = "Alice"
age = 20
info = f"{name} is {age} years old."

---

📘 Performance Comparison Table

Method	Recommended	Time Complexity
+	❌ for loops	O(n²) total
+=	❌ for loops	O(n²) total
"".join(list)	✔✔ Best	O(n)
StringIO	✔ for very large concatenation	O(n)
format(), f-strings	✔ for readability	O(n)

---

📘 Example to Show Performance Difference

❌ Slow method:

s = ""
for i in range(10000):
    s += "a"      # O(n²)

✔ Fast method:

parts = []
for i in range(10000):
    parts.append("a")
s = "".join(parts)   # O(n)

---

📘 String Concatenation as a Data Structure Problem

In DSA, strings are treated like arrays.

Concatenation involves:

1. Allocating memory for new string
2. Copying characters from both strings
3. Constructing final string
4. Returning new reference

This is why repeated concatenation becomes costly → repeated copying.

To optimize, Python uses:

• rope data structures in some languages
• StringBuilder in Java
• StringIO in Python
• join() which builds final string efficiently

---

📘 Summary (Exam Notes)

• String concatenation = joining two strings.
• Python strings are immutable → every concat creates new object.
• + and += are O(n) per operation → O(n²) in loops.
• "".join() is the most efficient → O(n).
• For large concatenation, use StringIO.
• Important concept in DSA because concatenation affects time complexity.

---