Goat Latin

Easy

#0778Time: O(L^2), where `L` is the length of the final Goat Latin sentence. In Java, concatenating strings in a loop (`result += newWord`) takes time proportional to the lengths of `result` and `newWord`. Since the length of `result` grows, the total time becomes quadratic in the final length. The final length can be `O(N + W^2)`, making this approach very slow for long sentences.Space: O(L), where `L` is the length of the final sentence. The final length `L` is `O(N + W^2)`, where `N` is the original sentence length and `W` is the number of words. This is because intermediate strings are created at each concatenation step, but the space is dominated by the final `result` string and the `words` array.

Data structures

String

Prompt

You are given a string sentence that consist of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to "Goat Latin" (a made-up language similar to Pig Latin.) The rules of Goat Latin are as follows:

If a word begins with a vowel ('a', 'e', 'i', 'o', or 'u'), append "ma" to the end of the word.
- For example, the word "apple" becomes "applema".
If a word begins with a consonant (i.e., not a vowel), remove the first letter and append it to the end, then add "ma".
- For example, the word "goat" becomes "oatgma".
Add one letter 'a' to the end of each word per its word index in the sentence, starting with 1.
- For example, the first word gets "a" added to the end, the second word gets "aa" added to the end, and so on.

Return the final sentence representing the conversion from sentence to Goat Latin.

Example 1:

Input: sentence = "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

Input: sentence = "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Constraints:

1 <= sentence.length <= 150
sentence consists of English letters and spaces.
sentence has no leading or trailing spaces.
All the words in sentence are separated by a single space.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves splitting the sentence into words and then, for each word, building the new "Goat Latin" word using standard string concatenation (+). The final sentence is also built by concatenating these modified words and spaces.

Algorithm

Create a Set containing all vowel characters (both lowercase and uppercase) for O(1) lookups.
Split the input sentence by spaces to get an array of words.
Initialize an empty string result to build the final sentence.
Initialize a string suffixA to "a". This will be used to add the trailing 'a's.
Loop through the words array with an index i.
For each word, check if its first character is in the vowel set.
If it's a vowel, create newWord by concatenating the word with "ma".
If it's a consonant, create newWord by taking the substring from the second character, appending the first character, and then appending "ma".
Append the current suffixA to newWord.
Append an additional 'a' to suffixA for the next iteration.
If it's not the first word (i > 0), append a space to the result string.
Append the newWord to the result string.
After the loop, return the result string.

Walkthrough

The core idea is to process the sentence word by word. First, we split the input sentence into an array of strings. We then iterate through this array. In each iteration, we transform the current word according to the Goat Latin rules.

A helper set is used to efficiently check for vowels. For a word starting with a vowel, we append "ma". For a word starting with a consonant, we move the first letter to the end and then append "ma". After this initial transformation, we append a number of 'a's corresponding to the word's 1-based index in the sentence.

These transformations are done using the + operator for strings. The final sentence is assembled by joining the transformed words with spaces. In Java, strings are immutable. This means that every time we use the + operator to concatenate strings, a new String object is created in memory, and the contents of the old strings are copied over. Doing this repeatedly in a loop is inefficient.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public String toGoatLatin(String sentence) {7        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));8        String[] words = sentence.split(" ");9        String result = "";10        String suffixA = "a";11 12        for (int i = 0; i < words.length; i++) {13            String word = words[i];14            String newWord;15            char firstChar = word.charAt(0);16 17            if (vowels.contains(firstChar)) {18                newWord = word + "ma";19            } else {20                newWord = word.substring(1) + firstChar + "ma";21            }22 23            newWord += suffixA;24            suffixA += "a";25 26            if (i > 0) {27                result += " ";28            }29            result += newWord;30        }31        return result;32    }33}

Complexity

Time

O(L^2), where `L` is the length of the final Goat Latin sentence. In Java, concatenating strings in a loop (`result += newWord`) takes time proportional to the lengths of `result` and `newWord`. Since the length of `result` grows, the total time becomes quadratic in the final length. The final length can be `O(N + W^2)`, making this approach very slow for long sentences.

Space

O(L), where `L` is the length of the final sentence. The final length `L` is `O(N + W^2)`, where `N` is the original sentence length and `W` is the number of words. This is because intermediate strings are created at each concatenation step, but the space is dominated by the final `result` string and the `words` array.

Trade-offs

Pros

Conceptually very simple and easy to write for beginners.

Cons

Highly inefficient in terms of time complexity due to the nature of immutable strings in languages like Java.
Creates a large number of temporary string objects, leading to performance degradation and increased garbage collection overhead.

This approach improves upon the naive method by using a StringBuilder to construct the final sentence. StringBuilder is mutable, allowing for efficient appends without creating new objects for each modification. This is the standard and recommended way to build strings in a loop in Java.

Algorithm

Create a Set of vowel characters for efficient O(1) lookup.
Split the input sentence by spaces to get an array of words.
Initialize an empty StringBuilder named result.
Loop through the words array with an index i from 0 to words.length - 1.
If this is not the first word (i > 0), append a space to result.
Get the current word and its firstChar.
Check if firstChar is a vowel.
If it is a vowel, append the entire word to result.
If it is a consonant, append the substring of the word starting from the second character, and then append the firstChar to result.
Append the string "ma" to result.
Use a nested loop to append the character 'a' i + 1 times to result.
After the main loop finishes, convert the result StringBuilder to a String using toString() and return it.

Walkthrough

The overall logic is the same as the naive approach: split the sentence, process each word, and join them back. The key difference is the use of StringBuilder for all string construction.

We initialize a StringBuilder to hold the final result. We iterate through the words of the sentence. For each word, we apply the Goat Latin rules. Instead of using + for concatenation, we use the append() method of the StringBuilder. The suffix of 'a's is also built and appended efficiently. We can use a nested loop to append the required number of 'a's for each word.

This avoids the creation of numerous intermediate String objects, making the process much faster and more memory-efficient. This approach is asymptotically optimal because the time complexity matches the size of the output string that must be constructed.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public String toGoatLatin(String sentence) {7        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));8        String[] words = sentence.split(" ");9        StringBuilder result = new StringBuilder();10 11        for (int i = 0; i < words.length; i++) {12            String word = words[i];13            char firstChar = word.charAt(0);14 15            if (i > 0) {16                result.append(" ");17            }18 19            if (vowels.contains(firstChar)) {20                result.append(word);21            } else {22                result.append(word.substring(1));23                result.append(firstChar);24            }25 26            result.append("ma");27 28            for (int j = 0; j <= i; j++) {29                result.append('a');30            }31        }32        return result.toString();33    }34}

Complexity

Time

O(N + W^2), where `N` is the length of the input sentence and `W` is the number of words. Splitting the sentence takes `O(N)`. The outer loop runs `W` times. Inside the loop, appending parts of the word takes `O(L_i)` where `L_i` is the length of the i-th word (sum of all `L_i` is `O(N)`). The inner loop for appending 'a's contributes `O(W^2)`. The total time is dominated by these operations. This is optimal as the output string has a length of `O(N + W^2)`.

Space

O(N + W^2), where `N` is the length of the input sentence and `W` is the number of words. The `words` array takes `O(N)` space. The `StringBuilder` needs space to store the final string. The length of the final string is the original length `N` plus `2*W` for "ma" plus `W*(W+1)/2` for the 'a's.

Trade-offs

Pros

Significantly more time-efficient than naive string concatenation.
Memory-efficient as it avoids creating many temporary objects.
It's the idiomatic and optimal way to build strings in loops in Java.

Cons

The code is slightly more verbose than the naive approach due to the use of the StringBuilder API.

Solutions

Solution

1class Solution {2public3  String toGoatLatin(String sentence) {4    List<String> ans = new ArrayList<>();5    Set<Character> vowels = new HashSet<>(6        Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));7    int i = 1;8    for (String word : sentence.split(" ")) {9      StringBuilder t = new StringBuilder();10      if (!vowels.contains(word.charAt(0))) {11        t.append(word.substring(1));12        t.append(word.charAt(0));13      } else {14        t.append(word);15      }16      t.append("ma");17      for (int j = 0; j < i; ++j) {18        t.append("a");19      }20      ++i;21      ans.add(t.toString());22    }23    return String.join(" ", ans);24  }25}

1class Solution:2    def toGoatLatin(self, sentence: str) -> str: ans = [] for i, word in enumerate(sentence . split()): if word . lower()[0] not in ['a', 'e', 'i', 'o', 'u']: word = word[1:] + word[0] word += 'ma' word += 'a' * (i + 1) ans . append(word) return ' ' . join(ans)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem