LeetCode 3856 - Trim Trailing Vowels

This problem asks us to remove all vowels that appear at the end of a given string. The input is a string s consisting only of lowercase English letters. A vowel is defined as one of the five characters: 'a', 'e', 'i', 'o', or 'u'.

leetcodeeasystring

LeetCode Problem 3856

Difficulty: 🟢 Easy
Topics: String

Solution

LeetCode 3856 - Trim Trailing Vowels

Problem Understanding

This problem asks us to remove all vowels that appear at the end of a given string.

The input is a string s consisting only of lowercase English letters. A vowel is defined as one of the five characters: 'a', 'e', 'i', 'o', or 'u'.

The goal is to repeatedly remove characters from the end of the string as long as the current last character is a vowel. The moment we encounter a non-vowel character, we stop removing characters and return the remaining prefix of the string.

For example, if the input is "idea", the last character is 'a', which is a vowel, so it is removed. The new last character becomes 'e', which is also a vowel, so it is removed as well. The remaining string is "id", whose last character is 'd', a consonant, so the process stops.

The constraints are very small:

  • 1 <= s.length <= 100
  • The string contains only lowercase English letters.

These constraints tell us that efficiency is not a major concern. Even a straightforward solution will easily fit within the limits. Nevertheless, we can still identify the most natural and efficient approach.

Several edge cases are important:

  • The string may already end with a consonant, in which case nothing should be removed.
  • The entire string may consist only of vowels, resulting in an empty string.
  • The string may contain vowels in the middle that should not be removed.
  • The string may have exactly one character.

Because the problem guarantees only lowercase English letters, we do not need to handle uppercase vowels or special characters.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly check the last character of the string. If it is a vowel, create a new string without that character and continue. Once the last character is not a vowel, return the current string.

This approach is correct because it exactly simulates the required operation. However, strings are immutable in many languages, including Python, so repeatedly creating shorter strings can cause unnecessary copying. If the string length were large, this would become inefficient.

Optimal Approach

Instead of repeatedly rebuilding the string, we can scan from right to left using an index.

Starting at the last position, we continue moving left while the current character is a vowel. When we find the first non-vowel character, everything to its left should remain. The answer is simply the substring ending at that position.

This avoids repeated string construction and performs only a single backward scan.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly creates shorter strings
Optimal O(n) O(1) auxiliary Single backward scan, one final substring operation

Algorithm Walkthrough

  1. Create a set containing the five vowels: 'a', 'e', 'i', 'o', and 'u'.
  2. Initialize an index i to the last position of the string, len(s) - 1.
  3. While i is valid and s[i] is a vowel, move the index one position to the left.
  4. When the loop stops, one of two things has happened:
  • We found a non-vowel character.
  • We moved past the beginning of the string because every character was a vowel.
  1. Return the substring s[:i + 1].
  2. If all characters were vowels, then i becomes -1, and s[:0] correctly returns the empty string.

Why it works

The algorithm maintains the invariant that every character to the right of index i is a trailing vowel that should be removed. By moving left while vowels are encountered, we identify the rightmost character that must remain. Returning the prefix ending at that position removes exactly the trailing vowels and leaves every other character unchanged.

Python Solution

class Solution:
    def trimTrailingVowels(self, s: str) -> str:
        vowels = {"a", "e", "i", "o", "u"}

        i = len(s) - 1

        while i >= 0 and s[i] in vowels:
            i -= 1

        return s[:i + 1]

The implementation begins by storing all vowels in a set, allowing constant time membership checks.

The variable i starts at the last character of the string. The loop continues moving left as long as the current character is a vowel. Once a consonant is found, or the entire string has been traversed, the loop terminates.

Finally, s[:i + 1] returns the desired prefix. If every character was removed, i becomes -1, and the slice correctly evaluates to an empty string.

Go Solution

func trimTrailingVowels(s string) string {
    vowels := map[byte]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
    }

    i := len(s) - 1

    for i >= 0 && vowels[s[i]] {
        i--
    }

    return s[:i+1]
}

The Go solution follows the same logic as the Python version. A map is used for constant time vowel lookups, and an index scans backward from the end of the string.

Go strings are byte indexed, which is safe here because the problem guarantees lowercase English letters only. No special Unicode handling is required.

Worked Examples

Example 1

Input: s = "idea"

Initial state:

Variable Value
s "idea"
i 3
Iteration s[i] Vowel? New i
1 'a' Yes 2
2 'e' Yes 1
3 'd' No Stop

Final result:

Expression Value
s[:2] "id"

Output: "id"

Example 2

Input: s = "day"

Initial state:

Variable Value
s "day"
i 2
Iteration s[i] Vowel? Action
1 'y' No Stop

Final result:

Expression Value
s[:3] "day"

Output: "day"

Example 3

Input: s = "aeiou"

Initial state:

Variable Value
s "aeiou"
i 4
Iteration s[i] Vowel? New i
1 'u' Yes 3
2 'o' Yes 2
3 'i' Yes 1
4 'e' Yes 0
5 'a' Yes -1

Final result:

Expression Value
s[:0] ""

Output: ""

Complexity Analysis

Measure Complexity Explanation
Time O(n) At most one backward scan through the string
Space O(1) Only a few variables and a fixed-size vowel set are used

The algorithm examines each character at most once while moving from right to left. The vowel set contains only five elements, so its size is constant. Therefore, the running time is linear in the string length, and the auxiliary space usage is constant.

Test Cases

sol = Solution()

assert sol.trimTrailingVowels("idea") == "id"          # example with multiple trailing vowels
assert sol.trimTrailingVowels("day") == "day"          # no trailing vowels
assert sol.trimTrailingVowels("aeiou") == ""           # all characters are vowels

assert sol.trimTrailingVowels("a") == ""              # single vowel
assert sol.trimTrailingVowels("b") == "b"             # single consonant

assert sol.trimTrailingVowels("apple") == "appl"      # one trailing vowel
assert sol.trimTrailingVowels("banana") == "banan"    # trailing vowel only
assert sol.trimTrailingVowels("code") == "cod"        # ending in e

assert sol.trimTrailingVowels("queue") == "q"         # many trailing vowels
assert sol.trimTrailingVowels("strength") == "strength"  # no vowels at end

assert sol.trimTrailingVowels("abcaeiou") == "abc"    # long vowel suffix
assert sol.trimTrailingVowels("z") == "z"             # smallest consonant case

Test Summary

Test Why
"idea" Multiple trailing vowels removed
"day" No removal needed
"aeiou" Entire string removed
"a" Single-character vowel
"b" Single-character consonant
"apple" One trailing vowel
"banana" Typical word ending with vowel
"code" Ends with vowel after consonants
"queue" Long consecutive vowel suffix
"strength" No trailing vowels at all
"abcaeiou" Large vowel suffix removal
"z" Smallest non-removal case

Edge Cases

Entire String Consists of Vowels

A common bug is failing to handle the situation where every character must be removed. For example, "aeiou" should produce an empty string. The implementation handles this naturally because the index eventually becomes -1, and the slice s[:0] returns the empty string.

String Already Ends with a Consonant

When the last character is not a vowel, nothing should be removed. Examples such as "day" and "strength" test this scenario. The loop never executes, and the full string is returned unchanged.

Single Character Strings

The smallest valid input has length one. If the character is a vowel, such as "a", the answer should be "". If it is a consonant, such as "b", the answer should remain "b". The backward scan correctly handles both cases without any special logic.

Vowels in the Middle of the String

Only trailing vowels should be removed. Internal vowels must remain untouched. For example, "banana" becomes "banan", not "bnn". Since the algorithm only scans from the end and never examines earlier vowels once a consonant is encountered, all non-trailing vowels are preserved correctly.