What is the time complexity of Valid Word?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Valid Word?

This problem uses String. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Valid Word?

Iterating through the word character by character allows checking for each validation rule simultaneously. Using boolean flags (`hasVowel`, `hasConsonant`) efficiently tracks the presence of vowels and consonants.

Which companies ask LeetCode 3136. Valid Word in interviews?

This problem is frequently asked at Expedia, UKG.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Valid Word - LeetCode 3136 Solution

Valid Word - Complete Solution Guide

Valid Word is LeetCode problem 3136, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

A word is considered valid if: It contains a minimum of 3 characters. It contains only digits (0-9), and English letters (uppercase and lowercase). It includes at least one vowel . It includes at least one consonant . 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 . A consonant is an English letter that is not a vowel. Example 1: Input: word = "234Adas" Output: true Explanation: This word

Detailed Explanation

The problem asks you to determine if a given word is 'valid' according to specific rules. A valid word must meet four criteria: 1. **Minimum Length:** It must contain at least 3 characters. 2. **Character Set:** It can only contain digits (0-9) and English letters (a-z, A-Z). 3. **Vowel Presence:** It must include at least one vowel (a, e, i, o, u, and their uppercase versions). 4. **Consonant Presence:** It must include at least one consonant (any letter that is not a vowel). The input is a single string `word`. The output is a boolean value: `true` if the word is valid, and `false` otherwise.

Solution Approach

The solution uses a single loop to iterate over each character in the input string. It first checks the length of the word. If it's less than 3, it immediately returns `false`. Otherwise, it initializes two boolean flags, `hasVowel` and `hasConsonant`, to `false`. Inside the loop, it first verifies if the current character is alphanumeric. If not, it returns `false`. If it is alphanumeric, it checks if it's a vowel and updates `hasVowel` accordingly. If it's a letter and not a vowel, it updates `hasConsonant`. Finally, it returns `true` only if both `hasVowel` and `hasConsonant` are `true`, indicating that the word meets all criteria.

Step-by-Step Algorithm

Check if the length of the word is less than 3. If so, return `false`.
Initialize boolean variables `hasVowel` and `hasConsonant` to `false`.
Iterate through each character in the word:
Check if the character is alphanumeric. If not, return `false`.
If the character is a vowel, set `hasVowel` to `true`.
If the character is a consonant, set `hasConsonant` to `true`.
After the loop, return `true` if both `hasVowel` and `hasConsonant` are `true`; otherwise, return `false`.

Key Insights

Iterating through the word character by character allows checking for each validation rule simultaneously.
Using boolean flags (`hasVowel`, `hasConsonant`) efficiently tracks the presence of vowels and consonants.
Early exit strategies (returning `false` immediately upon encountering an invalid character) optimize the solution.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: String.

Companies

Asked at: Expedia, UKG.

Valid Word | LeetCode 3136

Easy

String

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public boolean isValid(String word) {
        if (word.length() < 3) {
            return false;
        }

        boolean hasVowel = false;
        boolean hasConsonant = false;

        for (char c : word.toCharArray()) {
            if (!Character.isLetterOrDigit(c)) {
                return false;
            }

            if (Character.isLetter(c)) {
                char lowerC = Character.toLowerCase(c);
                if (lowerC == 'a' || lowerC == 'e' || lowerC == 'i' || lowerC == 'o' || lowerC == 'u') {
                    hasVowel = true;
                } else {
                    hasConsonant = true;
                }
            }
        }

        return hasVowel && hasConsonant;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 3136: Valid Word - Detailed explanation and solution approaches.

Topics

String

Companies

ExpediaUKG

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:3136

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Check if the length of the word is less than 3. If so, return `false`.
2
Initialize boolean variables `hasVowel` and `hasConsonant` to `false`.
3
Iterate through each character in the word:
4
Check if the character is alphanumeric. If not, return `false`.
5
If the character is a vowel, set `hasVowel` to `true`.
6
If the character is a consonant, set `hasConsonant` to `true`.
7
After the loop, return `true` if both `hasVowel` and `hasConsonant` are `true`; otherwise, return `false`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The loop iterates a maximum of n times (n being the word's length). All other operations take constant time. Therefore, the time complexity is linear. The space used is independent of the input size, making it constant.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using Regular Expressions

A regular expression could be used to check if the word matches the pattern of having at least 3 characters, containing only alphanumeric characters, at least one vowel, and at least one consonant. This could potentially be more concise but might be less readable for beginners.

Time: O(n)Space: O(1) or O(m) depending on the regex implementation, where m is the size of regex.

Trade-offs: Regular expressions can be more compact but might be less efficient and harder to understand than a straightforward iterative approach, especially for beginners.

✨

Key Insights

1Iterating through the word character by character allows checking for each validation rule simultaneously.
2Using boolean flags (`hasVowel`, `hasConsonant`) efficiently tracks the presence of vowels and consonants.
3Early exit strategies (returning `false` immediately upon encountering an invalid character) optimize the solution.

📚

Key Terms Explained

For Students

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Empty string or string with length less than 3: The code correctly handles this by returning `false`.
String containing only vowels or only consonants: The code correctly returns `false` in both scenarios because it requires both a vowel and a consonant.
String with non-alphanumeric characters: The code correctly returns `false` if any non-alphanumeric character is found.

⚠️

Common Mistakes to Avoid

✗Forgetting to check for the minimum length of 3 characters.

✗Incorrectly handling uppercase and lowercase vowels.

✗Not properly checking for non-alphanumeric characters.

✗Failing to check for both vowels and consonants; only checking for one or the other.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Input validation: This type of validation is crucial in many applications where user input needs to conform to specific patterns (e.g., password validation, username validation).

🏦Data cleaning: When processing text data, you might need to filter out words that don't meet certain criteria, ensuring data quality.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 16, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Valid Word"?

For this easy-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?