class Solution:
# time O(N+2K^2) space(N)
def toGoatLatin(self, S: str) -> str:
if not S:
return []
sen = S.split(' ') # O(N)
vo = {'a','e','i','o','u'}
res = list()
for idx, word in enumerate(sen):
if word[0].lower() not in vo: # edge case: Capical vowel
word = word[1:] + word[0] # O(w) w is word
word = word+'ma' + 'a'*(idx+1) # O(K^2) in total loop
res.append(word) # can't use res[idx] = word. will cause out of bound error
return ' '.join(res)