Valid Word - Solution & Explanation

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.