824. Goat Latin
Problem Description
This problem asks you to convert a given sentence into "Goat Latin", which is a made-up language with specific transformation rules.
Given a string sentence containing words separated by spaces (where each word consists only of lowercase and uppercase letters), you need to transform each word according to three rules:
Rule 1: Vowel vs Consonant
- If a word starts with a vowel (
'a','e','i','o', or'u'- case insensitive), append"ma"to the end of the word.- Example:
"apple"→"applema"
- Example:
- If a word starts with a consonant, remove the first letter, append it to the end, then add
"ma".- Example:
"goat"→"oatgma"
- Example:
Rule 2: Position-based 'a' Addition
- Add the letter
'a'to the end of each word based on its position in the sentence (1-indexed).- The 1st word gets one
'a'added - The 2nd word gets two
'a's added - The 3rd word gets three
'a's added, and so on
- The 1st word gets one
Example Walkthrough:
For the sentence "I speak Goat Latin":
"I"(1st word, starts with vowel) →"I"+"ma"+"a"="Imaa""speak"(2nd word, starts with consonant 's') →"peaks"+"ma"+"aa"="peaksmaaa""Goat"(3rd word, starts with consonant 'G') →"oatG"+"ma"+"aaa"="oatGmaaaa""Latin"(4th word, starts with consonant 'L') →"atinL"+"ma"+"aaaa"="atinLmaaaaa"
The final result would be: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
The task is to return the complete transformed sentence with all words converted to Goat Latin, maintaining the space-separated format.
How We Pick the Algorithm
Why Simulation / Basic DSA?
This problem maps to Simulation / Basic DSA through a short path in the full flowchart.
Each word's first letter and index drive a per-word transformation that is rejoined into Goat Latin.
Open in FlowchartIntuition
The problem requires us to transform each word independently according to specific rules, then reassemble them into a sentence. This naturally suggests processing the sentence word by word.
The key insight is that we need to:
- Split the sentence into individual words
- Transform each word based on its starting letter and position
- Join the transformed words back together
For each word transformation, we need to check if the first letter is a vowel. Since the problem states this check is case-insensitive (uppercase vowels like 'A', 'E' should also be treated as vowels), we can check the first character against a vowel set that contains both lowercase and uppercase vowels.
The position-dependent suffix (adding 'a's) suggests we need to track which word we're processing. When iterating through words, we can use the index to determine how many 'a's to append - the first word (index 0) gets 1 'a', the second word (index 1) gets 2 'a's, and so on. This is simply (index + 1) repetitions of 'a'.
The transformation process for each word follows a clear sequence:
- Check the first letter and apply the vowel/consonant rule
- Add
"ma" - Add the position-based
'a's
Since we're building a new sentence from transformed words, using a list to collect the transformed words and then joining them with spaces at the end is more efficient than string concatenation. This approach processes each word exactly once in a single pass through the sentence.
Solution Approach
The implementation follows a straightforward approach of processing each word individually:
Step 1: Split the sentence into words
sentence.split()
This breaks the input string into a list of words using spaces as delimiters.
Step 2: Process each word with enumeration
for i, word in enumerate(sentence.split()):
Using enumerate() gives us both the word and its index i (0-based), which we'll need for determining how many 'a's to append.
Step 3: Check if the word starts with a vowel
vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'} if word[0] not in vowels:
- The
vowelsset contains both lowercase and uppercase vowels, so the check is case-insensitive - If the first letter is NOT a vowel (consonant case), we need to move it to the end
Step 4: Apply consonant transformation if needed
word = word[1:] + word[0]
For consonants, slice the word from index 1 to the end (word[1:]) and append the first character (word[0]).
Step 5: Add the required suffixes
word += 'ma' word += 'a' * (i + 1)
- First append
'ma'to all words - Then append
'a'repeated(i + 1)times- Since
iis 0-based,(i + 1)gives us 1 for the first word, 2 for the second, etc.
- Since
Step 6: Collect and join the results
result_words.append(word) return ' '.join(result_words)
Store each transformed word in a list result_words, then join them with spaces to create the final sentence.
The algorithm processes each word exactly once, doing work proportional to the word's length plus the number of 'a's it receives. Because the number of added 'a's is 1 + 2 + ... + k for k words, the time and space complexity are O(n + k²), where n is the number of characters in the sentence.
Example Walkthrough
Let's trace through the solution with a simple example: "The quick fox"
Initial Setup:
- Input:
"The quick fox" - Create empty list
result_words = [] - Define vowels:
{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
Processing Word 1: "The" (index = 0)
- First letter: 'T'
- Is 'T' in
vowels? No (consonant) - Apply consonant rule:
"The"→"he" + "T"="heT" - Add "ma":
"heT" + "ma"="heTma" - Add position-based 'a's:
"heTma" + "a"*(0+1)="heTmaa" - Append to
result_words:result_words = ["heTmaa"]
Processing Word 2: "quick" (index = 1)
- First letter: 'q'
- Is 'q' a vowel? No (consonant)
- Apply consonant rule:
"quick"→"uick" + "q"="uickq" - Add "ma":
"uickq" + "ma"="uickqma" - Add position-based 'a's:
"uickqma" + "a"*(1+1)="uickqmaaa" - Append to
result_words:result_words = ["heTmaa", "uickqmaaa"]
Processing Word 3: "fox" (index = 2)
- First letter: 'f'
- Is 'f' a vowel? No (consonant)
- Apply consonant rule:
"fox"→"ox" + "f"="oxf" - Add "ma":
"oxf" + "ma"="oxfma" - Add position-based 'a's:
"oxfma" + "a"*(2+1)="oxfmaaaa" - Append to
result_words:result_words = ["heTmaa", "uickqmaaa", "oxfmaaaa"]
Final Step:
- Join with spaces:
" ".join(result_words)="heTmaa uickqmaaa oxfmaaaa"
Result: "heTmaa uickqmaaa oxfmaaaa"
Notice how each word gets progressively more 'a's at the end (1, 2, then 3), and consonant-starting words have their first letter moved to the end before adding "ma".
Solution Implementation
1class Solution:
2 def toGoatLatin(self, sentence: str) -> str:
3 """
4 Convert a sentence to Goat Latin following these rules:
5 1. If word begins with vowel, append "ma" to the end
6 2. If word begins with consonant, move first letter to end, then add "ma"
7 3. Add one 'a' for each word's index (1-based): first word gets 'a', second gets 'aa', etc.
8
9 Args:
10 sentence: Input string containing words separated by spaces
11
12 Returns:
13 String with words converted to Goat Latin
14 """
15 # Define set of vowels for O(1) lookup
16 vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
17
18 # List to store transformed words
19 result_words = []
20
21 # Process each word with its index
22 for index, word in enumerate(sentence.split()):
23 # Check if first character is a consonant (not a vowel)
24 if word[0] not in vowels:
25 # Move first character to end for consonants
26 word = word[1:] + word[0]
27
28 # Append "ma" to all words
29 word += 'ma'
30
31 # Append 'a' repeated (index + 1) times
32 word += 'a' * (index + 1)
33
34 # Add transformed word to result list
35 result_words.append(word)
36
37 # Join all words with spaces and return
38 return ' '.join(result_words)
391class Solution {
2 public String toGoatLatin(String sentence) {
3 // List to store transformed words
4 List<String> transformedWords = new ArrayList<>();
5
6 // Set containing all vowels (both lowercase and uppercase)
7 Set<Character> vowelSet = new HashSet<>(
8 Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')
9 );
10
11 // Counter for the position of each word (1-indexed)
12 int wordIndex = 1;
13
14 // Process each word in the sentence
15 for (String word : sentence.split(" ")) {
16 StringBuilder goatLatinWord = new StringBuilder();
17
18 // Check if the first character is a vowel
19 if (!vowelSet.contains(word.charAt(0))) {
20 // If consonant: move first character to the end
21 goatLatinWord.append(word.substring(1));
22 goatLatinWord.append(word.charAt(0));
23 } else {
24 // If vowel: keep the word as is
25 goatLatinWord.append(word);
26 }
27
28 // Add "ma" suffix to all words
29 goatLatinWord.append("ma");
30
31 // Add 'a' repeated based on word position (1st word: 1 'a', 2nd word: 2 'a's, etc.)
32 for (int j = 0; j < wordIndex; j++) {
33 goatLatinWord.append("a");
34 }
35
36 // Increment word index for next iteration
37 wordIndex++;
38
39 // Add the transformed word to the result list
40 transformedWords.add(goatLatinWord.toString());
41 }
42
43 // Join all transformed words with spaces and return
44 return String.join(" ", transformedWords);
45 }
46}
471#include <string>
2#include <vector>
3#include <sstream>
4#include <cctype>
5
6class Solution {
7public:
8 /**
9 * Converts a sentence to "Goat Latin" following these rules:
10 * 1. If a word begins with a vowel, append "ma" to the end
11 * 2. If a word begins with a consonant, remove the first letter and append it to the end, then add "ma"
12 * 3. Add one 'a' to the end of each word per its word index (1-indexed)
13 *
14 * @param sentence - Input sentence to convert to Goat Latin
15 * @return The sentence converted to Goat Latin
16 */
17 string toGoatLatin(string sentence) {
18 // Split the sentence into individual words
19 vector<string> words;
20 stringstream ss(sentence);
21 string word;
22
23 while (ss >> word) {
24 words.push_back(word);
25 }
26
27 // Process each word according to Goat Latin rules
28 string result = "";
29
30 for (int index = 0; index < words.size(); index++) {
31 string currentWord = words[index];
32 string transformedWord;
33
34 // Check if the first character is a vowel (case-insensitive)
35 char firstChar = tolower(currentWord[0]);
36 bool startsWithVowel = (firstChar == 'a' || firstChar == 'e' ||
37 firstChar == 'i' || firstChar == 'o' ||
38 firstChar == 'u');
39
40 if (startsWithVowel) {
41 // Rule 1: Word starts with vowel - keep as is
42 transformedWord = currentWord;
43 } else {
44 // Rule 2: Word starts with consonant - move first letter to end
45 transformedWord = currentWord.substr(1) + currentWord[0];
46 }
47
48 // Add "ma" suffix
49 transformedWord += "ma";
50
51 // Add position-based 'a' characters (1-indexed)
52 for (int i = 0; i <= index; i++) {
53 transformedWord += 'a';
54 }
55
56 // Add to result with space separator (except for first word)
57 if (index > 0) {
58 result += " ";
59 }
60 result += transformedWord;
61 }
62
63 return result;
64 }
65};
661/**
2 * Converts a sentence to "Goat Latin" following these rules:
3 * 1. If a word begins with a vowel, append "ma" to the end
4 * 2. If a word begins with a consonant, remove the first letter and append it to the end, then add "ma"
5 * 3. Add one 'a' to the end of each word per its word index (1-indexed)
6 *
7 * @param sentence - Input sentence to convert to Goat Latin
8 * @returns The sentence converted to Goat Latin
9 */
10function toGoatLatin(sentence: string): string {
11 // Split the sentence into individual words
12 const words: string[] = sentence.split(' ');
13
14 // Process each word according to Goat Latin rules
15 const goatLatinWords: string[] = words.map((word: string, index: number) => {
16 let transformedWord: string;
17
18 // Check if the first character is a vowel (case-insensitive)
19 const startsWithVowel: boolean = /[aeiou]/i.test(word[0]);
20
21 if (startsWithVowel) {
22 // Rule 1: Word starts with vowel - keep as is
23 transformedWord = word;
24 } else {
25 // Rule 2: Word starts with consonant - move first letter to end
26 transformedWord = word.slice(1) + word[0];
27 }
28
29 // Add "ma" suffix and position-based 'a' characters (1-indexed)
30 const numberOfAs: string = 'a'.repeat(index + 1);
31 const finalWord: string = `${transformedWord}ma${numberOfAs}`;
32
33 return finalWord;
34 });
35
36 // Join the transformed words back into a sentence
37 return goatLatinWords.join(' ');
38}
39Time and Space Complexity
Time Complexity: O(n + k²)
Let n be the total number of characters in the input sentence and k the number of words.
- Splitting the sentence:
O(n) - For each word, checking the first letter against the
vowelsset isO(1) - String slicing
word[1:] + word[0]and appending'ma'takeO(w)wherewis the length of the word, which sums toO(n)over all words - Appending
'a' * (index + 1)takesO(index), and summing over all words gives1 + 2 + ... + k = k(k+1)/2, which isO(k²) - The final
jointakes time proportional to the output length,O(n + k²)
The number of added 'a' characters grows quadratically with the number of words, so the total is O(n + k²). Since k can be about n / 2 (for example, a sentence of single-letter words), this is O(n²) in the worst case.
Space Complexity: O(n + k²)
- The
result_wordslist stores the transformed words, which contain the originalncharacters plus2kcharacters of'ma'andk(k+1)/2added'a's - The output string has the same length
Therefore, the overall space complexity is O(n + k²), which is O(n²) in the worst case.
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Case Sensitivity in Vowel Detection
Pitfall: A common mistake is only checking for lowercase vowels, forgetting that words can start with uppercase vowels (like "I" or "Apple").
Incorrect approach:
if word[0] not in ['a', 'e', 'i', 'o', 'u']: # Misses uppercase vowels! word = word[1:] + word[0]
Solution: Either check both cases explicitly or convert to lowercase for comparison:
# Option 1: Include both cases in the set vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'} if word[0] not in vowels: word = word[1:] + word[0] # Option 2: Convert to lowercase for checking if word[0].lower() not in ['a', 'e', 'i', 'o', 'u']: word = word[1:] + word[0]
2. Off-by-One Error with 'a' Suffix Count
Pitfall: Using the wrong index calculation for appending 'a's, typically forgetting that enumerate starts at 0 while the problem requires 1-based indexing.
Incorrect approach:
for i, word in enumerate(sentence.split()):
# ... process word ...
word += 'a' * i # Wrong! First word gets 0 'a's instead of 1
Solution: Add 1 to the enumeration index:
for i, word in enumerate(sentence.split()):
# ... process word ...
word += 'a' * (i + 1) # Correct: First word (i=0) gets 1 'a'
3. Modifying the Original Word Variable
Pitfall: Trying to build the result by repeatedly concatenating to the same string variable can lead to confusion about what transformations have been applied.
Potentially confusing approach:
for i, word in enumerate(sentence.split()):
if word[0].lower() not in vowels:
word = word[1:] + word[0]
word = word + 'ma'
word = word + 'a' * (i + 1)
# Multiple reassignments can be error-prone
Solution: Use clear, sequential transformations or build a new string:
for i, word in enumerate(sentence.split()):
# Build transformed word step by step with clear logic
if word[0] not in vowels:
transformed = word[1:] + word[0]
else:
transformed = word
transformed += 'ma' + 'a' * (i + 1)
result_words.append(transformed)
4. Empty String or Single Character Edge Cases
Pitfall: Not considering edge cases like empty strings or single-character words when slicing.
Potential issue:
word = word[1:] + word[0] # What if word is empty or has only 1 character?
Solution: No special handling is needed. sentence.split() never produces empty words, and for a single-letter word such as "b", word[1:] is "", so word[1:] + word[0] is "b" again. The word then gets "ma" and its 'a's appended as usual.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapGiven a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity describes how the time needed
Want a Structured Path to Master System Design Too? Don’t Miss This!