Facebook Pixel

824. Goat Latin

EasyString
LeetCode ↗

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"
  • If a word starts with a consonant, remove the first letter, append it to the end, then add "ma".
    • Example: "goat" → "oatgma"

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

Example Walkthrough:

For the sentence "I speak Goat Latin":

  1. "I" (1st word, starts with vowel) → "I" + "ma" + "a" = "Imaa"
  2. "speak" (2nd word, starts with consonant 's') → "peaks" + "ma" + "aa" = "peaksmaaa"
  3. "Goat" (3rd word, starts with consonant 'G') → "oatG" + "ma" + "aaa" = "oatGmaaaa"
  4. "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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Parsesymbols?noDirectsimulation?yesSimulation /Basic DSA

Each word's first letter and index drive a per-word transformation that is rejoined into Goat Latin.

Open in Flowchart

Intuition

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:

  1. Split the sentence into individual words
  2. Transform each word based on its starting letter and position
  3. 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:

  1. Check the first letter and apply the vowel/consonant rule
  2. Add "ma"
  3. 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.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

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 vowels set 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 i is 0-based, (i + 1) gives us 1 for the first word, 2 for the second, etc.

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)
39
1class 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}
47
1#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};
66
1/**
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}
39

Time 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 vowels set is O(1)
  • String slicing word[1:] + word[0] and appending 'ma' take O(w) where w is the length of the word, which sums to O(n) over all words
  • Appending 'a' * (index + 1) takes O(index), and summing over all words gives 1 + 2 + ... + k = k(k+1)/2, which is O(k²)
  • The final join takes 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_words list stores the transformed words, which contain the original n characters plus 2k characters of 'ma' and k(k+1)/2 added '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 Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Given 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
12
1public 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}
16
1function 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}
16

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More