You are given a sentence consisting of words separated by spaces. You must transform it into Goat Latin according to these rules:

For each word in order:

1. If the word begins with a vowel (a, e, i, o, u — case insensitive), append "ma" to the end.
2. If it begins with a consonant, move the first letter to the end and then append "ma".
3. After applying rule 1 or 2, append 'a' repeated according to the word index (starting at 1).
4. Words must remain separated by spaces in the final output.

Example:

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

Another example:

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

---

Problem Understanding

Important details:

• Word order remains unchanged
• Case sensitivity is preserved
• Vowel check must be case-insensitive
• 'a' repetitions depend on position of word
• Spaces remain single spaces — no trimming, no collapsing
• Only the first character determines the transformation

---

Logic Explained in Simple English

Here’s the simplest way to think about this transformation:

1. Split the sentence into individual words.
2. Process each word one by one.
3. For each word:
   • Check if the first letter is a vowel
   • If vowel:
     • Keep the word as is, then add "ma"
   • If consonant:
     • Remove the first letter, put it at the end, then add "ma"
4. Figure out how many 'a' characters to append:
   • First word gets "a"
   • Second word gets "aa"
   • Third gets "aaa"
   • and so on…
5. Join the processed words back together with spaces.
6. Return the final sentence.

Why this works:

• Each rule maps cleanly to a small string manipulation step
• Word position determines 'a' count
• No complex parsing needed

---

Step-by-Step Approach

1. Define a set of vowels for quick lookup
2. Split the input sentence into words
3. Initialize a StringBuilder for output
4. Loop through words with index
5. For each word:
   • Determine vowel vs consonant
   • Transform appropriately
   • Append "ma"
   • Append correct number of 'a'
   • Append space if not last word
6. Convert builder to string and return

---

Java Implementation

class Solution {
    public String toGoatLatin(String sentence) {
        Set<Character> vowels = new HashSet<>(Arrays.asList(
            'a','e','i','o','u','A','E','I','O','U'
        ));
        
        String[] words = sentence.split(" ");
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            
            if (vowels.contains(word.charAt(0))) {
                result.append(word);
            } else {
                result.append(word.substring(1)).append(word.charAt(0));
            }
            
            result.append("ma");
            
            for (int j = 0; j <= i; j++) {
                result.append('a');
            }
            
            if (i < words.length - 1) {
                result.append(" ");
            }
        }
        
        return result.toString();
    }
}

---

Dry Run Example

Input:

"I speak Goat Latin"

Split:

["I", "speak", "Goat", "Latin"]

Word 1: “I”

• starts with vowel
• transform → "I" + "ma" + "a"
  Result so far:

"Imaa"

Word 2: “speak”

• starts with consonant
• transform:
  • remove ‘s’, append at end → "peaks"
  • add "ma"
  • add "aa"
    Result:

"Imaa peaksmaaa"

Word 3: “Goat”

• consonant
• "oatG" + "ma" + "aaa"
  Result:

"Imaa peaksmaaa oatGmaaaa"

Word 4: “Latin”

• consonant
• "atinL" + "ma" + "aaaa"
  Final output:

"Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

---

Time and Space Complexity

Time Complexity

O(n)

n = total number of characters
Each character processed once

Space Complexity

O(n)

Output string requires proportional space

---

Common Mistakes and How to Avoid Them

Mistake 1: Treating vowel check as case-sensitive

Must include uppercase vowel handling

Mistake 2: Adding wrong number of 'a' characters

Count is based on word index starting at 1

Mistake 3: Adding extra spaces

Only add spaces between words

Mistake 4: Modifying word internals incorrectly

Only the first letter moves, nothing else

Mistake 5: Forgetting that single-letter words are valid

Example:

"I" → "Imaa"