DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Goat Latin

easyStringsMeta Production Engineer

Problem statement

You get a sentence of words separated by single spaces. Each word contains only English letters. Convert every word with these rules, then join the words back with single spaces:

  1. If the word starts with a vowel (a, e, i, o, u, in either case), append "ma".
  2. Otherwise, move its first letter to the end, then append "ma".
  3. Finally, append the letter a once for the first word, twice for the second word, and so on.

Return the converted sentence.

Examples

Example 1

Input: sentence = "Deploy the app"

Output: "eployDmaa hetmaaa appmaaaa"

Explanation: "Deploy" becomes "eployD" + "ma" + "a". "the" becomes "het" + "ma" + "aa". "app" starts with a vowel, so it becomes "app" + "ma" + "aaa".

Example 2

Input: sentence = "I ran"

Output: "Imaa anrmaaa"

Hints

Approach

Same rules, but build the output efficiently: collect converted words in a list (or a StringBuilder) and join once at the end, and grow the a suffix by one character per word instead of recreating it.

  1. Keep suffix = "" and a list out.
  2. For each word: add one "a" to suffix; convert the word; append word + "ma" + suffix to out.
  3. Return " ".join(out).

The output itself has length L = O(n + w²) for n input characters and w words (the a suffixes add 1 + 2 + … + w characters), so linear in the output is the best possible.

ComplexityTime O(L)Space O(L)
Python
class Solution:
def toGoatLatin(self, sentence: str) -> str:
vowels = set("aeiouAEIOU")
out = []
suffix = ""
for word in sentence.split(" "):
suffix += "a" # one more 'a' per word
if word[0] in vowels:
out.append(word + "ma" + suffix)
else:
out.append(word[1:] + word[0] + "ma" + suffix)
return " ".join(out)

Follow-up questions

  • Keep punctuation attached to the end of a word in place, for example "app," becomes "appma," plus the suffix.
  • Write the reverse function that turns Goat Latin back into the original sentence.

Frequently asked questions

The length of the output. It includes the growing a suffixes, which add up to w(w + 1)/2 characters for w words, so the output can be much longer than the input.

Repeated result = result + ... copies the whole string built so far each time. With a list and one join (or a StringBuilder), each character is written once.

It checks careful, rule-by-rule string handling with no clever algorithm to hide behind: the same care you need when rewriting log lines, renaming resources to a convention, or templating config values. Interviewers watch for the uppercase vowel case and for efficient string building.