# LeetCode 824: Goat Latin

## Problem Restatement

We are given a sentence made of words separated by single spaces.

Each word contains only uppercase and lowercase English letters.

We need to convert every word into Goat Latin using these rules:

1. If a word starts with a vowel, append `"ma"`.
2. If a word starts with a consonant, move the first letter to the end, then append `"ma"`.
3. Append `'a'` characters based on the word position. The first word gets `"a"`, the second gets `"aa"`, the third gets `"aaa"`, and so on.

The vowel check is case-insensitive. The vowels are:

```python
a, e, i, o, u
```

The official examples include `"I speak Goat Latin"` converting to `"Imaa peaksmaaa oatGmaaaa atinLmaaaaa"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `sentence` |
| Output | The sentence converted to Goat Latin |
| Word separator | Single spaces |
| Vowel rule | Check first letter case-insensitively |
| Position rule | Append `i` copies of `'a'` for the `i`th word |

## Examples

Example 1:

```python
sentence = "I speak Goat Latin"
```

Word by word:

| Word | Transformation |
|---|---|
| `"I"` | `"I" + "ma" + "a"` |
| `"speak"` | `"peak" + "s" + "ma" + "aa"` |
| `"Goat"` | `"oat" + "G" + "ma" + "aaa"` |
| `"Latin"` | `"atin" + "L" + "ma" + "aaaa"` |

The answer is:

```python
"Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
```

Example 2:

```python
sentence = "The quick brown fox jumped over the lazy dog"
```

The answer is:

```python
"heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"
```

## First Thought: Process Each Word

The rules apply independently to each word.

So we can:

1. Split the sentence into words.
2. Convert each word.
3. Join the converted words with spaces.

There is no need for recursion, dynamic programming, or a complex data structure.

## Key Insight

Only the first character of each word decides the main transformation.

If it is a vowel, the word stays in the same order.

If it is a consonant, the first character moves to the end.

After that, every word receives `"ma"` and a position-based suffix of `'a'`.

## Algorithm

Create a vowel set:

```python
vowels = {"a", "e", "i", "o", "u"}
```

Split the sentence:

```python
words = sentence.split()
```

For each word at index `i`:

1. If the first character is a vowel after lowercasing:

```python
word[0].lower() in vowels
```

keep the word as is.

2. Otherwise, move the first character to the end:

```python
word = word[1:] + word[0]
```

3. Append:

```python
"ma" + "a" * (i + 1)
```

4. Store the converted word.

Finally, join the results with spaces.

## Correctness

The algorithm processes the sentence word by word in original order.

For each word, it checks the first character case-insensitively. If the first character is a vowel, it appends `"ma"` without changing the word order, exactly as required.

If the first character is a consonant, it removes that character from the front and appends it to the end before adding `"ma"`, exactly as required.

The algorithm uses the zero-based index `i`, so the number of appended `'a'` characters is `i + 1`. This matches the one-based word position rule.

Since every word is transformed according to all three rules and the transformed words are joined with spaces in the same order, the returned sentence is the correct Goat Latin sentence.

## Complexity

Let `n = len(sentence)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed a constant number of times |
| Space | `O(n)` | The output and list of transformed words use linear space |

## Implementation

```python
class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        vowels = {"a", "e", "i", "o", "u"}
        result = []

        for i, word in enumerate(sentence.split()):
            if word[0].lower() not in vowels:
                word = word[1:] + word[0]

            word += "ma"
            word += "a" * (i + 1)

            result.append(word)

        return " ".join(result)
```

## Code Explanation

The vowel set stores lowercase vowels only:

```python
vowels = {"a", "e", "i", "o", "u"}
```

We lowercase only the first character during the check:

```python
word[0].lower() not in vowels
```

This handles both uppercase and lowercase words.

For consonant-starting words, we move the first character to the end:

```python
word = word[1:] + word[0]
```

Then every word receives `"ma"`:

```python
word += "ma"
```

The position suffix is based on `i + 1`:

```python
word += "a" * (i + 1)
```

Finally, the transformed words are joined with one space:

```python
return " ".join(result)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.toGoatLatin(
        "I speak Goat Latin"
    ) == "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

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

    assert s.toGoatLatin("Apple") == "Applemaa"
    assert s.toGoatLatin("goat") == "oatgmaa"
    assert s.toGoatLatin("a b c") == "amaa bmaaa cmaaaa"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"I speak Goat Latin"` | Official mixed vowel and consonant example |
| Long sentence | Checks increasing `'a'` suffixes |
| `"Apple"` | Uppercase vowel handling |
| `"goat"` | Consonant movement |
| `"a b c"` | Position-based suffix rule |