Finally got AC after 3 WAs. Sharing what I missed.

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