LeetCode 3136 - Valid Word

The problem asks us to determine whether a given string qualifies as a "valid word" according to four specific rules. First, the word must contain at least 3 characters. Any string shorter than 3 is automatically invalid.

leetcodeeasystring

LeetCode Problem 3136

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to determine whether a given string qualifies as a "valid word" according to four specific rules.

First, the word must contain at least 3 characters. Any string shorter than 3 is automatically invalid.

Second, every character in the string must be either:

  • A lowercase English letter
  • An uppercase English letter
  • A digit from 0 to 9

If the string contains any other symbol such as @, #, or $, the word is invalid immediately.

Third, the word must contain at least one vowel. The valid vowels are:

  • Lowercase: a, e, i, o, u
  • Uppercase: A, E, I, O, U

Fourth, the word must contain at least one consonant. A consonant is any English alphabet letter that is not a vowel.

The input is a single string word, and the output is a boolean:

  • Return true if all conditions are satisfied
  • Return false otherwise

The constraints are very small:

  • 1 <= word.length <= 20

This tells us that performance is not a concern. Even a straightforward scan of the string is more than fast enough.

Several edge cases are important:

  • Strings shorter than 3 characters
  • Strings containing invalid symbols such as $
  • Strings containing only digits
  • Strings containing vowels but no consonants
  • Strings containing consonants but no vowels
  • Mixed uppercase and lowercase vowels

A naive implementation can easily make mistakes if it:

  • Treats digits as consonants
  • Forgets uppercase vowels
  • Fails to reject invalid symbols immediately

Approaches

Brute Force Approach

A brute force approach would repeatedly scan the string multiple times.

One pass could check whether all characters are valid. Another pass could search for vowels. A third pass could search for consonants. We could also separately check the length requirement.

This approach is correct because every rule is verified independently. However, it performs unnecessary repeated work by traversing the same string multiple times.

Even though the constraints are tiny and this would still pass easily, it is not the cleanest or most efficient solution.

Optimal Approach

The key observation is that all conditions can be checked in a single traversal of the string.

While iterating through each character:

  • Reject invalid characters immediately
  • Track whether we have seen at least one vowel
  • Track whether we have seen at least one consonant

Digits are allowed, but they do not contribute to either the vowel or consonant requirement.

At the end of the scan:

  • The word is valid only if both flags are true

This approach is optimal because it minimizes both time and space usage while keeping the implementation simple and readable.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Multiple passes over the string
Optimal O(n) O(1) Single pass with boolean tracking

Algorithm Walkthrough

  1. First, check whether the length of the string is less than 3. If it is, return false immediately because the minimum length requirement is violated.
  2. Create a set containing all vowels:
a, e, i, o, u, A, E, I, O, U

Using a set allows constant time membership checks. 3. Initialize two boolean variables:

  • has_vowel = False
  • has_consonant = False

These variables track whether the required character types have appeared. 4. Iterate through every character in the string. 5. For each character:

  • If it is neither a letter nor a digit, return false immediately because the string contains an invalid symbol.

  • If it is a letter:

  • If it exists in the vowel set, set has_vowel = True

  • Otherwise, it must be a consonant, so set has_consonant = True

  1. Digits are allowed, so no additional action is needed when encountering them.
  2. After processing all characters, return:
has_vowel AND has_consonant

Why it works

The algorithm maintains two important properties while scanning the string:

  • has_vowel is true if at least one vowel has appeared
  • has_consonant is true if at least one consonant has appeared

At the same time, invalid characters are rejected immediately. Since every character is examined exactly once, and every rule is verified during that traversal, the final result is correct.

Python Solution

class Solution:
    def isValid(self, word: str) -> bool:
        if len(word) < 3:
            return False

        vowels = set("aeiouAEIOU")

        has_vowel = False
        has_consonant = False

        for char in word:
            if not char.isalnum():
                return False

            if char.isalpha():
                if char in vowels:
                    has_vowel = True
                else:
                    has_consonant = True

        return has_vowel and has_consonant

The implementation begins by handling the shortest invalid strings immediately. This prevents unnecessary processing.

The vowels set stores all uppercase and lowercase vowels so membership checks are efficient and simple.

Two boolean flags track whether the required letter categories have been encountered.

The loop processes each character exactly once:

  • char.isalnum() verifies that the character is either a letter or digit
  • char.isalpha() distinguishes letters from digits
  • Vowels and consonants are classified appropriately

Finally, the method returns True only when both required conditions are satisfied.

Go Solution

func isValid(word string) bool {
    if len(word) < 3 {
        return false
    }

    vowels := map[rune]bool{
        'a': true, 'e': true, 'i': true, 'o': true, 'u': true,
        'A': true, 'E': true, 'I': true, 'O': true, 'U': true,
    }

    hasVowel := false
    hasConsonant := false

    for _, char := range word {
        isLetter := (char >= 'a' && char <= 'z') ||
            (char >= 'A' && char <= 'Z')

        isDigit := (char >= '0' && char <= '9')

        if !isLetter && !isDigit {
            return false
        }

        if isLetter {
            if vowels[char] {
                hasVowel = true
            } else {
                hasConsonant = true
            }
        }
    }

    return hasVowel && hasConsonant
}

The Go version follows the same algorithmic structure as the Python solution.

One important difference is that Go does not provide direct methods like isalnum() or isalpha() for rune values in the same way Python does for strings. Instead, the implementation manually checks ASCII ranges to determine whether a character is a letter or digit.

The vowel lookup uses a map[rune]bool for efficient membership testing.

Since the input size is tiny, there are no concerns about performance or memory overhead.

Worked Examples

Example 1

Input:

word = "234Adas"

Initial state:

Variable Value
has_vowel False
has_consonant False

Processing steps:

Character Type Action has_vowel has_consonant
2 Digit Allowed False False
3 Digit Allowed False False
4 Digit Allowed False False
A Vowel Set vowel flag True False
d Consonant Set consonant flag True True
a Vowel Already true True True
s Consonant Already true True True

Final result:

True

Example 2

Input:

word = "b3"

Length check:

Condition Result
len(word) < 3 True

The algorithm immediately returns:

False

Example 3

Input:

word = "a3$e"

Initial state:

Variable Value
has_vowel False
has_consonant False

Processing steps:

Character Type Action
a Vowel Set vowel flag
3 Digit Allowed
$ Invalid symbol Return false immediately

Final result:

False

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once
Space O(1) Only a few boolean variables and a small vowel set are used

The algorithm scans the string exactly one time. Since each operation inside the loop is constant time, the total runtime grows linearly with the length of the string.

The extra memory usage remains constant because the vowel set size never changes and only two boolean flags are stored.

Test Cases

solution = Solution()

assert solution.isValid("234Adas") == True   # valid mixed string
assert solution.isValid("b3") == False       # too short
assert solution.isValid("a3$e") == False     # invalid symbol

assert solution.isValid("abc") == True       # simple valid lowercase
assert solution.isValid("AE1") == False      # vowels only, no consonant
assert solution.isValid("bcdf") == False     # consonants only, no vowel
assert solution.isValid("123") == False      # digits only
assert solution.isValid("a1b") == True       # minimal valid case
assert solution.isValid("A1b") == True       # uppercase vowel
assert solution.isValid("u9Z") == True       # uppercase consonant
assert solution.isValid("@ab") == False      # invalid leading symbol
assert solution.isValid("ab#") == False      # invalid trailing symbol
assert solution.isValid("a") == False        # single character
assert solution.isValid("12a") == False      # vowel but no consonant
assert solution.isValid("12b") == False      # consonant but no vowel
Test Why
"234Adas" Standard valid example
"b3" Length smaller than 3
"a3$e" Contains invalid symbol
"abc" Simple valid lowercase word
"AE1" Only vowels present
"bcdf" Only consonants present
"123" Digits alone are insufficient
"a1b" Smallest valid mixed case
"A1b" Uppercase vowel handling
"u9Z" Uppercase consonant handling
"@ab" Invalid symbol at start
"ab#" Invalid symbol at end
"a" Single-character edge case
"12a" Missing consonant
"12b" Missing vowel

Edge Cases

One important edge case is very short strings such as "a" or "b3". A careless implementation might continue processing characters even though the word can never become valid. The solution handles this immediately with an early length check.

Another important case is strings containing invalid characters like "a3$e" or "ab#". Since the problem allows only letters and digits, these inputs must return false. The implementation checks every character with isalnum() in Python or explicit ASCII checks in Go, guaranteeing invalid symbols are rejected immediately.

A third important edge case is strings containing only digits, such as "123". Digits are allowed characters, but they do not count as vowels or consonants. Some incorrect solutions accidentally classify non-vowel characters as consonants. This implementation avoids that mistake by only classifying alphabetic characters as vowels or consonants.

Another subtle case is uppercase vowels like "A1b". If the vowel set only contains lowercase letters, uppercase vowels would be misclassified as consonants. The implementation explicitly includes both uppercase and lowercase vowels, ensuring correct behavior for mixed-case input.