In Python, s += "x" in a loop is O(n²) because strings are immutable. Use a list and join once at the end for O(n).
What Is It?
String concatenation with += creates a brand-new string every time, copying all previous characters. Do this n times and you've copied 1 + 2 + ... + n characters — that's O(n²).
The fix: collect parts in a list (append is O(1) amortized), then call "".join(parts) once at the end. Total cost: O(n). Same result, quadratically faster.