Python tests look okay to me, assuming they've been fixed in the last five years. Just commenting here to note that.

Absolutely.
The spirit of the exercice is tu use reg expressions and it's also more direct, even though Regex is somehow a bit more complex.

You realize complexity is measured in terms of worse case. So worst case is O(N) if you're iterating through the list. There's no such thing as O(2N) factors drop off in complexity measures.

Linq Select has an override that gives you the index of the current item in the selector (that index is the same number of times you need to repeat). I used Repeat didn't realize there was a string constructor overload that does the same.

Also totally forgot about string.Join. Much cleaner code than I wrote on my first pass.

Maybe we should add this to the edgecases.