Clean Python solution, beats most submissions.

Work with character counts or indices rather than building new strings in the loop; string concatenation inside loops is what usually causes TLE here.