LeetCode 824 - Goat Latin

LeetCode Problem 824

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

This problem asks us to transform a given sentence into a fictional language called Goat Latin, following a specific set of string manipulation rules.

The input is a string called sentence, where words are separated by a single space. Every word contains only English alphabetic characters, meaning uppercase and lowercase letters. We must process each word individually and then combine the transformed words back into a final sentence.

For every word, the transformation depends on whether the first character is a vowel or a consonant:

• If the word starts with a vowel (a, e, i, o, u, case insensitive), we simply append "ma" to the end of the word.
• If the word starts with a consonant, we remove the first character, place it at the end of the word, and then append "ma".

After this first transformation, we must append a sequence of 'a' characters based on the word's position in the sentence. The first word gets one 'a', the second gets two 'a', and so forth.

For example:

• "apple" starts with a vowel, so it becomes "applema".
• "goat" starts with a consonant, so moving the first letter to the back gives "oatg", then adding "ma" gives "oatgma".

The final output is the transformed sentence where every word has undergone these modifications and remains separated by spaces.

The constraints tell us several important things:

• sentence.length <= 150, which is extremely small.
• Words are guaranteed to be separated by exactly one space.
• There are no leading or trailing spaces.
• Every word contains only letters.

Because the input size is tiny, efficiency is not a major concern. Even a less optimized solution would easily pass. However, we should still aim for a clean and efficient linear-time implementation.

Several edge cases are important to recognize upfront. A sentence containing only one word must still receive the correct 'a' suffix. Uppercase vowels such as "I" or "Apple" must be treated as vowels, meaning case sensitivity must be handled carefully. Very short words, including single-character words like "I" or "a", should not break the transformation logic when moving consonants. The problem guarantees valid formatting, so we do not need to handle multiple spaces or empty words.

Approaches

Brute Force Approach

A brute-force way to solve this problem is to repeatedly rebuild strings character by character. For each word, we could manually inspect the first character, reconstruct the transformed word using loops, append "ma", then append the required number of 'a' characters by another loop.

For example, when handling a consonant-starting word, we could create a new string by iterating from the second character onward, then append the first character manually. Likewise, for the growing 'a' suffix, we could repeatedly concatenate one 'a' at a time.

This approach works because it directly follows the transformation rules. However, repeated string concatenation can become inefficient in languages where strings are immutable, since every concatenation may allocate a new string. Although the constraints are small enough that this still passes comfortably, it is unnecessarily cumbersome.

Optimal Approach

The key observation is that this is fundamentally a single-pass string transformation problem. We only need to process each word once.

We can split the sentence into words, determine whether each word starts with a vowel using a hash set for constant-time lookup, apply the required transformation, append the correct number of 'a' characters using string multiplication, and store the result in a list.

Finally, we join all transformed words with spaces.

This approach is efficient because each word is visited exactly once, and every operation performed is proportional to the size of the word itself.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated string concatenation may repeatedly rebuild strings
Optimal	O(n)	O(n)	Single pass through words with efficient string building

Here, n represents the total number of characters in the sentence.

Algorithm Walkthrough

1. Create a set containing all vowels in both lowercase and uppercase form.

We use a set because membership checking is O(1). This lets us quickly determine whether a word begins with a vowel. 2. Split the sentence into individual words.

Since the problem guarantees words are separated by single spaces and there are no leading or trailing spaces, using .split() gives us exactly the words we need. 3. Create an empty list to store transformed words.

Instead of repeatedly concatenating strings, we accumulate processed words in a list and join them at the end for efficiency. 4. Iterate through the words with their index.

The index matters because each word gets an increasing number of 'a' characters. Since indexing starts at 0, we add 1 to get the correct word position. 5. For each word, check whether its first character is a vowel.

• If it is a vowel, append "ma" directly.
• If it is a consonant, move the first character to the end and append "ma".

6. Append the required number of 'a' characters.

If this is the i-th word in zero-based indexing, append 'a' * (i + 1). 7. Add the transformed word to the results list. 8. Join all transformed words with spaces and return the final string.

Why it works

The algorithm works because every word is transformed independently according to the exact Goat Latin rules. For each word, we correctly distinguish between vowels and consonants, apply the required modification, and append the appropriate number of 'a' characters based on position. Since every word is processed once and added back in order, the resulting sentence preserves the original structure while satisfying all transformation requirements.

Python Solution

class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        vowels = set("aeiouAEIOU")
        words = sentence.split()
        transformed_words = []

        for index, word in enumerate(words, start=1):
            if word[0] in vowels:
                transformed_word = word + "ma"
            else:
                transformed_word = word[1:] + word[0] + "ma"

            transformed_word += "a" * index
            transformed_words.append(transformed_word)

        return " ".join(transformed_words)

The implementation begins by creating a set of vowels that includes both lowercase and uppercase letters. This ensures words like "I" and "Apple" are correctly identified as vowel-starting words.

Next, the sentence is split into words using .split(). Because the problem guarantees clean spacing, this produces an accurate list of words without additional preprocessing.

We then iterate through the words using enumerate(..., start=1). Starting at 1 makes the index directly correspond to the required number of 'a' characters, avoiding an extra adjustment later.

Inside the loop, we inspect the first character of the word. If it is a vowel, we append "ma" directly. Otherwise, we move the first character to the end and append "ma".

Finally, we append the required 'a' suffix using string multiplication, add the transformed word to the result list, and return the final sentence using " ".join(...).

Go Solution

import "strings"

func toGoatLatin(sentence string) string {
	vowels := map[byte]bool{
		'a': true, 'e': true, 'i': true, 'o': true, 'u': true,
		'A': true, 'E': true, 'I': true, 'O': true, 'U': true,
	}

	words := strings.Split(sentence, " ")
	result := make([]string, 0, len(words))

	for i, word := range words {
		var transformed string

		if vowels[word[0]] {
			transformed = word + "ma"
		} else {
			transformed = word[1:] + string(word[0]) + "ma"
		}

		transformed += strings.Repeat("a", i+1)
		result = append(result, transformed)
	}

	return strings.Join(result, " ")
}

The Go implementation follows the same logic as the Python version but adapts to Go language conventions.

A map[byte]bool is used for vowel lookup because strings in Go are byte slices, and accessing word[0] returns a byte. Since the input only contains English letters, byte indexing is perfectly safe.

Instead of Python string multiplication, Go uses strings.Repeat("a", i+1) to generate the repeated 'a' suffix. The final sentence is assembled efficiently using strings.Join().

There are no concerns about integer overflow due to the tiny constraints, and nil handling is unnecessary because the input guarantees a valid non-empty sentence.

Worked Examples

Example 1

Input:

"I speak Goat Latin"

Step	Word	Starts With Vowel?	Transformation	Added 'a's	Result
1	"I"	Yes	"Ima"	"a"	"Imaa"
2	"speak"	No	"peaksma"	"aa"	"peaksmaaa"
3	"Goat"	No	"oatGma"	"aaa"	"oatGmaaaa"
4	"Latin"	No	"atinLma"	"aaaa"	"atinLmaaaaa"

Final output:

"Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2

Input:

"The quick brown fox jumped over the lazy dog"

Step	Word	Transformation	Suffix	Final Word
1	"The"	"heTma"	"a"	"heTmaa"
2	"quick"	"uickqma"	"aa"	"uickqmaaa"
3	"brown"	"rownbma"	"aaa"	"rownbmaaaa"
4	"fox"	"oxfma"	"aaaa"	"oxfmaaaaa"
5	"jumped"	"umpedjma"	"aaaaa"	"umpedjmaaaaaa"
6	"over"	"overma"	"aaaaaa"	"overmaaaaaaa"
7	"the"	"hetma"	"aaaaaaa"	"hetmaaaaaaaa"
8	"lazy"	"azylma"	"aaaaaaaa"	"azylmaaaaaaaaa"
9	"dog"	"ogdma"	"aaaaaaaaa"	"ogdmaaaaaaaaaa"

Final output:

"heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed a constant number of times
Space	O(n)	Additional storage is used for transformed words

The algorithm runs in linear time because every word is processed once, and the total amount of work across all transformations is proportional to the total number of characters in the sentence. The repeated 'a' additions are also bounded by the number of words, which is still linear relative to input size.

The space complexity is linear because we store transformed words before joining them into the final output string.

Test Cases

solution = Solution()

assert solution.toGoatLatin("I speak Goat Latin") == (
    "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
)  # Provided example 1

assert solution.toGoatLatin(
    "The quick brown fox jumped over the lazy dog"
) == (
    "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa "
    "umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa "
    "azylmaaaaaaaaa ogdmaaaaaaaaaa"
)  # Provided example 2

assert solution.toGoatLatin("a") == "amaa"  
# Single vowel word

assert solution.toGoatLatin("I") == "Imaa"  
# Single uppercase vowel

assert solution.toGoatLatin("dog") == "ogdma" + "a"  
# Single consonant word

assert solution.toGoatLatin("Apple") == "Applemaa"  
# Uppercase vowel handling

assert solution.toGoatLatin("goat") == "oatgmaa"  
# Consonant transformation

assert solution.toGoatLatin("a b c") == "amaa bmacaa cmaaaa"  
# Multiple single-letter words

assert solution.toGoatLatin("Hello World") == (
    "elloHmaa orldWmaaa"
)  # Uppercase consonants

Test	Why
"I speak Goat Latin"	Validates provided example
"The quick brown fox jumped over the lazy dog"	Validates long multi-word sentence
"a"	Tests single vowel word
"I"	Tests uppercase vowel
"dog"	Tests consonant movement
"Apple"	Ensures uppercase vowels are handled
"goat"	Validates consonant transformation
"a b c"	Tests multiple single-letter words
"Hello World"	Tests uppercase consonants

Edge Cases

Single-Character Words

Words like "I" or "a" can be a source of bugs because moving the first character in a consonant transformation may accidentally produce an invalid substring operation. In this implementation, slicing safely handles these cases. For example, "b"[1:] becomes an empty string, making the transformed result "bma" before suffix addition.

Uppercase Letters

The problem allows both lowercase and uppercase English letters. A naive implementation that checks only lowercase vowels would incorrectly treat "Apple" or "I" as consonant-starting words. This implementation explicitly includes uppercase vowels in the vowel set, ensuring correct classification.

Single Word Sentences

A sentence containing only one word still needs the first positional suffix, which is exactly one 'a'. By using enumerate(..., start=1) in Python and i + 1 in Go, the implementation naturally handles this case without requiring special logic.

All Consonant or All Vowel Words

A sentence where every word starts with the same category can expose hidden branching errors. For example, all-vowel sentences must always append "ma" directly, while all-consonant sentences must consistently move the first character. Since every word is checked independently against the vowel set, both situations are handled correctly and consistently.