Goat Latin

Difficulty: Easy | Acceptance: 70.00% | Paid: No Topics: String

You are given a string sentence that consists of words separated by single spaces. Each word consists of lowercase and uppercase English letters.

Convert sentence to Goat Latin according to the following rules:

• 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, 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.

• Examples
• Constraints
• Approach 1: Iterative Split and Join
• Approach 2: Two Pointers Simulation

Examples

Input: sentence = "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
Explanation:
The word "I" starts with a vowel, so add "ma" and an "a" -> "Imaa".
The word "speak" starts with a consonant, move the 's' to the end, add "ma" and "aa" -> "peaksmaaa".
The word "Goat" starts with a consonant, move the 'G' to the end, add "ma" and "aaa" -> "oatGmaaaa".
The word "Latin" starts with a consonant, move the 'L' to the end, add "ma" and "aaaa" -> "atinLmaaaaa".

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.

Approach 1: Iterative Split and Join

Intuition The most straightforward way to process words individually is to split the input string into an array of words. This allows us to easily access each word by its index, which is required to determine the number of trailing ‘a’s.

Steps

• Split the input sentence by spaces to obtain a list of words.
• Iterate through the list of words, keeping track of the 1-based index.
• For each word, check if the first character is a vowel (case-insensitive).
• If it is a vowel, append “ma” to the word.
• If it is a consonant, move the first character to the end of the word, then append “ma”.
• Append a string of ‘a’ characters with length equal to the current index.
• Join the transformed words back into a single string with spaces and return it.

class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        vowels = set('aeiouAEIOU')
        words = sentence.split()
        result = []
        
        for i, word in enumerate(words):
            if word[0] not in vowels:
                word = word[1:] + word[0]
            
            word += 'ma'
            word += 'a' * (i + 1)
            result.append(word)
            
        return ' '.join(result)

Complexity

• Time: O(N), where N is the length of the sentence. We iterate through the characters to split and then through each word to transform it.
• Space: O(N), to store the list of words and the resulting string.
• Notes: This approach is highly readable and leverages built-in string manipulation functions effectively.

Approach 2: Two Pointers Simulation

Intuition Instead of splitting the string into an array, which requires extra memory allocation, we can process the string in a single pass using two pointers. One pointer marks the start of a word, and the other finds the end. This simulates the split operation manually.

Steps

• Initialize an empty result string and a word counter starting at 1.
• Iterate through the sentence with a pointer i.
• When a non-space character is found, mark it as the start of the word.
• Move the end pointer until a space or the end of the string is reached.
• Extract the substring representing the word.
• Apply the vowel/consonant transformation rules.
• Append “ma” and the appropriate number of ‘a’s based on the word counter.
• Append the transformed word to the result, followed by a space if it is not the last word.
• Increment the word counter and repeat until the end of the sentence.

class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        vowels = set('aeiouAEIOU')
        result = []
        n = len(sentence)
        i = 0
        word_index = 1
        
        while i < n:
            # Skip spaces
            while i < n and sentence[i] == ' ':
                i += 1
            
            if i >= n:
                break
                
            start = i
            while i < n and sentence[i] != ' ':
                i += 1
            
            word = sentence[start:i]
            
            if word[0] not in vowels:
                word = word[1:] + word[0]
            
            word += 'ma' + 'a' * word_index
            result.append(word)
            word_index += 1
            
        return ' '.join(result)

Complexity

• Time: O(N), where N is the length of the sentence. We traverse the string exactly once.
• Space: O(N), to store the output string. This approach avoids the auxiliary array of words used in the split method, potentially reducing overhead slightly.
• Notes: This is a memory-optimized version of the split approach, useful in environments where memory allocation is expensive.