BeginnerArrays & Strings
Build strings with a list, then join
Adding to a string in a loop can quietly cost O(n²). Collect pieces in a list and join once at the end.
The idea
Strings can't be changed in place in Python, Java or JavaScript. `s += ch` creates a brand new string and copies everything so far, every time. In a loop that's 1 + 2 + 3 + … + n copies: O(n²).
Collect the pieces in a list (or a StringBuilder in Java) and join them once at the end. Appending to a list is O(1), so the whole thing is O(n).
Worked example
Reversing the words of “the sky is blue”
- Split → ['the', 'sky', 'is', 'blue']
- Reverse the list → ['blue', 'is', 'sky', 'the']
- Join once with spaces → 'blue is sky the'
In code (Python)
def reverse_words(s):
return " ".join(reversed(s.split()))
# Building character by character:
def keep_letters(s):
out = []
for ch in s:
if ch.isalpha():
out.append(ch)
return "".join(out)How to spot it
- You build a result string inside a loop.
Common mistakes
- `result = result + ch` in a long loop.
- Forgetting `split()` with no argument already drops repeated spaces.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →