Asked in my Google OA last week.

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