# Goat Latin
**Difficulty:** EASY
[External](https://leetcode.com/problems/goat-latin)
Canonical: https://scaleengineer.com/dsa/problems/goat-latin
**Data structures:** String
---
## Problem
You are given a string `sentence` that consist of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to "Goat Latin" (a made-up language similar to Pig Latin.) The rules of Goat Latin are as follows:

* If a word begins with a vowel (`'a'`, `'e'`, `'i'`, `'o'`, or `'u'`), append `"ma"` to the end of the word.  
  * For example, the word `"apple"` becomes `"applema"`.
* If a word begins with a consonant (i.e., not a vowel), remove the first letter and append it to the end, then add `"ma"`.  
  * For example, the word `"goat"` becomes `"oatgma"`.
* Add one letter `'a'` to the end of each word per its word index in the sentence, starting with `1`.  
  * For example, the first word gets `"a"` added to the end, the second word gets `"aa"` added to the end, and so on.

Return _the final sentence representing the conversion from sentence to Goat Latin_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `1 <= sentence.length <= 150`
* `sentence` consists of English letters and spaces.
* `sentence` has no leading or trailing spaces.
* All the words in `sentence` are separated by a single space.

# Approaches
## Naive String Concatenation
This approach involves splitting the sentence into words and then, for each word, building the new "Goat Latin" word using standard string concatenation (`+`). The final sentence is also built by concatenating these modified words and spaces.
**Time:** O(L^2), where `L` is the length of the final Goat Latin sentence. In Java, concatenating strings in a loop (`result += newWord`) takes time proportional to the lengths of `result` and `newWord`. Since the length of `result` grows, the total time becomes quadratic in the final length. The final length can be `O(N + W^2)`, making this approach very slow for long sentences. · **Space:** O(L), where `L` is the length of the final sentence. The final length `L` is `O(N + W^2)`, where `N` is the original sentence length and `W` is the number of words. This is because intermediate strings are created at each concatenation step, but the space is dominated by the final `result` string and the `words` array.
**Pros:** Conceptually very simple and easy to write for beginners.
**Cons:** Highly inefficient in terms of time complexity due to the nature of immutable strings in languages like Java.; Creates a large number of temporary string objects, leading to performance degradation and increased garbage collection overhead.
### Explanation
The core idea is to process the sentence word by word. First, we split the input `sentence` into an array of strings. We then iterate through this array. In each iteration, we transform the current word according to the Goat Latin rules.

A helper set is used to efficiently check for vowels. For a word starting with a vowel, we append "ma". For a word starting with a consonant, we move the first letter to the end and then append "ma". After this initial transformation, we append a number of 'a's corresponding to the word's 1-based index in the sentence.

These transformations are done using the `+` operator for strings. The final sentence is assembled by joining the transformed words with spaces. In Java, strings are immutable. This means that every time we use the `+` operator to concatenate strings, a new `String` object is created in memory, and the contents of the old strings are copied over. Doing this repeatedly in a loop is inefficient.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

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(" ");
        String result = "";
        String suffixA = "a";

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            String newWord;
            char firstChar = word.charAt(0);

            if (vowels.contains(firstChar)) {
                newWord = word + "ma";
            } else {
                newWord = word.substring(1) + firstChar + "ma";
            }

            newWord += suffixA;
            suffixA += "a";

            if (i > 0) {
                result += " ";
            }
            result += newWord;
        }
        return result;
    }
}
```
### Algorithm
- Create a `Set` containing all vowel characters (both lowercase and uppercase) for O(1) lookups.
- Split the input `sentence` by spaces to get an array of `words`.
- Initialize an empty string `result` to build the final sentence.
- Initialize a string `suffixA` to "a". This will be used to add the trailing 'a's.
- Loop through the `words` array with an index `i`.
- For each `word`, check if its first character is in the vowel set.
- If it's a vowel, create `newWord` by concatenating the `word` with "ma".
- If it's a consonant, create `newWord` by taking the substring from the second character, appending the first character, and then appending "ma".
- Append the current `suffixA` to `newWord`.
- Append an additional 'a' to `suffixA` for the next iteration.
- If it's not the first word (`i > 0`), append a space to the `result` string.
- Append the `newWord` to the `result` string.
- After the loop, return the `result` string.

## Efficient String Building with StringBuilder
This approach improves upon the naive method by using a `StringBuilder` to construct the final sentence. `StringBuilder` is mutable, allowing for efficient appends without creating new objects for each modification. This is the standard and recommended way to build strings in a loop in Java.
**Time:** O(N + W^2), where `N` is the length of the input sentence and `W` is the number of words. Splitting the sentence takes `O(N)`. The outer loop runs `W` times. Inside the loop, appending parts of the word takes `O(L_i)` where `L_i` is the length of the i-th word (sum of all `L_i` is `O(N)`). The inner loop for appending 'a's contributes `O(W^2)`. The total time is dominated by these operations. This is optimal as the output string has a length of `O(N + W^2)`. · **Space:** O(N + W^2), where `N` is the length of the input sentence and `W` is the number of words. The `words` array takes `O(N)` space. The `StringBuilder` needs space to store the final string. The length of the final string is the original length `N` plus `2*W` for "ma" plus `W*(W+1)/2` for the 'a's.
**Pros:** Significantly more time-efficient than naive string concatenation.; Memory-efficient as it avoids creating many temporary objects.; It's the idiomatic and optimal way to build strings in loops in Java.
**Cons:** The code is slightly more verbose than the naive approach due to the use of the `StringBuilder` API.
### Explanation
The overall logic is the same as the naive approach: split the sentence, process each word, and join them back. The key difference is the use of `StringBuilder` for all string construction.

We initialize a `StringBuilder` to hold the final result. We iterate through the words of the sentence. For each word, we apply the Goat Latin rules. Instead of using `+` for concatenation, we use the `append()` method of the `StringBuilder`. The suffix of 'a's is also built and appended efficiently. We can use a nested loop to append the required number of 'a's for each word.

This avoids the creation of numerous intermediate `String` objects, making the process much faster and more memory-efficient. This approach is asymptotically optimal because the time complexity matches the size of the output string that must be constructed.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

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];
            char firstChar = word.charAt(0);

            if (i > 0) {
                result.append(" ");
            }

            if (vowels.contains(firstChar)) {
                result.append(word);
            } else {
                result.append(word.substring(1));
                result.append(firstChar);
            }

            result.append("ma");

            for (int j = 0; j <= i; j++) {
                result.append('a');
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Create a `Set` of vowel characters for efficient O(1) lookup.
- Split the input `sentence` by spaces to get an array of `words`.
- Initialize an empty `StringBuilder` named `result`.
- Loop through the `words` array with an index `i` from 0 to `words.length - 1`.
- If this is not the first word (`i > 0`), append a space to `result`.
- Get the current `word` and its `firstChar`.
- Check if `firstChar` is a vowel.
- If it is a vowel, append the entire `word` to `result`.
- If it is a consonant, append the substring of the `word` starting from the second character, and then append the `firstChar` to `result`.
- Append the string "ma" to `result`.
- Use a nested loop to append the character 'a' `i + 1` times to `result`.
- After the main loop finishes, convert the `result` `StringBuilder` to a `String` using `toString()` and return it.

# Solutions
### Java

```java
class Solution {
public
  String toGoatLatin(String sentence) {
    List<String> ans = new ArrayList<>();
    Set<Character> vowels = new HashSet<>(
        Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
    int i = 1;
    for (String word : sentence.split(" ")) {
      StringBuilder t = new StringBuilder();
      if (!vowels.contains(word.charAt(0))) {
        t.append(word.substring(1));
        t.append(word.charAt(0));
      } else {
        t.append(word);
      }
      t.append("ma");
      for (int j = 0; j < i; ++j) {
        t.append("a");
      }
      ++i;
      ans.add(t.toString());
    }
    return String.join(" ", ans);
  }
}

```

### Python

```python
class Solution:
    def toGoatLatin(self, sentence: str) -> str: ans = [] for i, word in enumerate(sentence . split()): if word . lower()[0] not in ['a', 'e', 'i', 'o', 'u']: word = word[1:] + word[0] word += 'ma' word += 'a' * (i + 1) ans . append(word) return ' ' . join(ans)

```