A word is considered valid if:
You are given a string word.
Return true if word is valid, otherwise, return false.
Notes:
'a', 'e', 'i', 'o', 'u', and their uppercases are vowels.
Example 1:
Input: word = "234Adas"
Output: true
Explanation:
This word satisfies the conditions.
Example 2:
Input: word = "b3"
Output: false
Explanation:
The length of this word is fewer than 3, and does not have a vowel.
Example 3:
Input: word = "a3$e"
Output: false
Explanation:
This word contains a '$' character and does not have a consonant.
Constraints:
1 <= word.length <= 20word consists of English uppercase and lowercase letters, digits, '@', '#', and '$'.Problem Overview: You receive a string word. A word is considered valid if it has length at least 3, contains only digits or English letters, and includes at least one vowel and one consonant. Digits are allowed but do not count toward vowel or consonant requirements. The task is to scan the string and verify these rules efficiently.
Approach 1: Iterative Character Check (O(n) time, O(1) space)
The direct solution walks through the string once and inspects each character. Use simple character checks: isalnum-style logic to ensure every character is a letter or digit. While iterating, maintain two boolean flags: one for detecting a vowel (a, e, i, o, u, case-insensitive) and another for detecting a consonant. Digits are ignored for these counters but still validated as allowed characters. If any character is neither a digit nor a letter, the word becomes invalid immediately. After the scan finishes, the word is valid only if both vowel and consonant flags are true.
This approach relies purely on linear iteration and constant state tracking. The algorithm touches each character exactly once, giving O(n) time complexity where n is the length of the string, and O(1) space since only a few flags are stored. This pattern appears frequently in string validation problems where constraints depend on character categories.
Approach 2: Optimized Early Exit (O(n) time, O(1) space)
This version follows the same core idea but exits as soon as the answer becomes impossible or confirmed. During iteration, immediately return false when encountering a non‑alphanumeric character. Track vowel and consonant presence the same way as before. The optimization comes from checking conditions during the scan: if invalid characters appear, terminate instantly instead of finishing the loop. In practice this reduces work for malformed inputs.
Although the worst‑case complexity remains O(n), early termination improves average performance when invalid characters occur near the beginning. The algorithm still uses constant memory, making it ideal for constrained environments. This pattern is common in input validation tasks across string processing and iteration-based problems.
Recommended for interviews: The expected solution is a single linear scan with character classification. Interviewers want to see that you validate constraints while iterating and maintain minimal state (vowel/consonant flags). A brute force multi-pass check would work but signals weaker problem structuring. The optimized single-pass approach demonstrates clean reasoning, correct use of string traversal, and attention to edge cases such as digits and special characters.
In this method, we iterate through each character of the word to check for validity. We utilize flags to confirm the presence of at least one vowel and one consonant while ensuring all characters are either letters or digits. The function will early exit if conditions for a valid word are met within the iteration.
This C function checks if the word is valid by iterating over each character. It uses strlen to check the length, strchr to identify vowels, isdigit, and isalpha from the C standard library to check each character's type. If the word is less than 3 characters or contains a non-alphanumeric character, it returns false. Otherwise, it maintains flags to check for both vowels and consonants.
Time Complexity: O(n), where n represents the total number of characters in the word.
Space Complexity: O(1), as it uses a fixed amount of extra space for flag variables.
This method enhances performance by exiting the loop as soon as the necessary conditions for a valid word are identified. By bundling multiple checks, this approach minimizes unnecessary operations and provides rapid results.
In this optimized C function, character checks are grouped logically to ensure minimal iterations. The presence of both vowels and consonants ends the loop early. Using strchr assists in direct checks for vowels.
Time Complexity: O(n), with n as the character count in the word, but may exit earlier.
Space Complexity: O(1), with minimal storage requirements for conditions checks.
First, we check if the length of the string is less than 3. If it is, we return false.
Next, we iterate through the string, checking if each character is a letter or a number. If it's not, we return false. Otherwise, we check if the character is a vowel. If it is, we set has_vowel to true. If it's not, we set has_consonant to true.
Finally, if both has_vowel and has_consonant are true, we return true. Otherwise, we return false.
The time complexity is O(n), and the space complexity is O(1). Where n is the length of the string.
| Approach | Complexity |
|---|---|
| Iterative Character Check | Time Complexity: O(n), where n represents the total number of characters in the word. Space Complexity: O(1), as it uses a fixed amount of extra space for flag variables. |
| Optimized Early Exit | Time Complexity: O(n), with n as the character count in the word, but may exit earlier. Space Complexity: O(1), with minimal storage requirements for conditions checks. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Character Check | O(n) | O(1) | General case when validating characters and tracking vowel/consonant presence in a single pass |
| Optimized Early Exit | O(n) | O(1) | Preferred when invalid characters may appear early and you want immediate termination |
Valid Word | Easy | Leetcode 3136 | codestorywithMIK • codestorywithMIK • 4,676 views views
Watch 9 more video solutions →Practice Valid Word with our built-in code editor and test cases.
Practice on FleetCode