Valid Word

Easy

Microsoft

6 views

Topics:

Strings

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 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 <= 20
word consists of English uppercase and lowercase letters, digits, '@', '#', and '$'.

Valid Word

Easy

Microsoft

6 views

Topics:

Strings

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 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 <= 20
word consists of English uppercase and lowercase letters, digits, '@', '#', and '$'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What defines a 'valid word' in this context? Are there specific criteria like length, character set, or presence in a dictionary?
Can the input contain empty strings or null values, and if so, how should I handle them?
Are there any limitations on the size or format of the input? For example, is it a single string, a list of strings, or something else?
If no valid word exists based on the defined criteria, what should the function return (e.g., null, empty string, error)?
Are there any specific constraints or conditions that constitute a 'valid' word? For example, must it only contain letters, or can it contain other characters?

Brute Force Solution

Approach

The brute force approach to checking if a word is valid is like trying every possible combination. It involves generating all potential arrangements and then methodically verifying each one. This continues until a valid arrangement is found, or until all arrangements are exhausted.

Here's how the algorithm would work step-by-step:

Start with the word you need to validate and a set of rules that describe what makes the word valid.
Consider every possible alteration you can make to the word based on the validation rules. This might include rearranging letters or changing some letters.
For each of these alterations, check whether the altered word is valid according to the rules.
If at any point you discover a combination which breaks the validity rules, stop immediately and try the next possible alteration.
Continue this process of generating and testing until either you find a valid arrangement or you have tried all possible arrangements.
If a valid arrangement is found, return true; otherwise, return false if you have exhausted all options without finding one.

Code Implementation

def is_valid_word_brute_force(word, validation_rules):
    from itertools import permutations

    # Generate all possible permutations of the word
    all_possible_arrangements = [''.join(permutation) for permutation in permutations(word)]

    for arrangement in all_possible_arrangements:
        # Check if the current arrangement is valid based on the rules

        is_arrangement_valid = True

        for rule in validation_rules:
            if not rule(arrangement):
                is_arrangement_valid = False
                break

        # If the current arrangement is valid, return True

        if is_arrangement_valid:
            return True

    # If none of the arrangements are valid, return False
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(P * V) – The brute force approach involves generating P possible arrangements of the input word, where P depends on the specific rules for creating variations. For each of these P arrangements, we perform a validation check which we denote as V. The algorithm continues until a valid arrangement is found or all P arrangements have been checked. Therefore, in the worst-case scenario, we check all P arrangements with cost V each, resulting in a time complexity of O(P * V).

Space Complexity

O(N!) – The brute force approach described generates all possible arrangements of the word. In the worst case, where no valid arrangement is found until all permutations are explored, the algorithm implicitly stores all N! permutations either for comparison or as function call parameters (if using recursion). Therefore, the space complexity is directly proportional to the number of permutations. The space complexity is O(N!), where N is the length of the word being validated, due to the potential storage of all possible arrangements in memory or on the call stack during the permutation generation and validation process.

Optimal Solution

Approach

The key to solving this problem efficiently is to focus on confirming the existence of the characters, rather than manipulating the string a lot. We'll leverage a technique of counting to achieve this. Instead of trying to build new words, we'll focus on checking if the required characters exist and are available to build our target word.

Here's how the algorithm would work step-by-step:

First, count how many times each character appears in the source text.
Then, examine each character in the target word you're trying to create.
For each character in the target word, check if the source text has enough of that character available.
If the source text doesn't have enough of a certain character, then the target word can't be made.
If the source text has enough of all the characters needed for the target word, then the target word can be made.

Code Implementation

def is_valid_word(source_text, target_word):
    source_character_counts = {}

    for char in source_text:
        source_character_counts[char] = source_character_counts.get(char, 0) + 1

    # Iterate through characters of target.
    for char in target_word:
        if char not in source_character_counts or source_character_counts[char] == 0:

            return False

        # Decrement source count as char is used.
        source_character_counts[char] -= 1

    # If loop completes, target word is valid.
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m + n) – The algorithm first counts the frequency of each character in the source text. This step iterates through the source text of length 'm', so it takes O(m) time. Then, the algorithm iterates through the target word of length 'n' to check if the source text has enough of each character. This step takes O(n) time. Therefore, the overall time complexity is O(m + n), representing the sum of the lengths of the source text and the target word.

Space Complexity

O(1) – The algorithm uses a character count map (likely implemented as a dictionary or hash map), and the size of this map is bounded by the size of the character set used in the input text. Since the character set is typically fixed (e.g., ASCII or Unicode), the space used by this map is constant regardless of the length of the input text or target word. Therefore, the auxiliary space is constant, O(1).

Edge Cases

Case	How to Handle
Empty word list	Return false immediately as an empty list means no valid word can exist.
Empty target word	Return true if the word list is also empty, otherwise return false.
Target word is shorter than the shortest word in the word list	The solution should efficiently recognize this and return false as no combination can create the target.
Target word is longer than the concatenation of all words	Return false, since the target cannot be formed by the available words.
Word list contains duplicate words	The algorithm needs to correctly account for word frequency and potential permutations in the word list.
Target word contains repeated characters not present in the word list	Check for sufficient counts of each character in the word list to form the target.
Very long word list and very long target word, approaching memory limits	Optimize memory usage by using efficient data structures and avoid unnecessary string copies.
Word list contains words that are prefixes or suffixes of other words in the list	The solution should handle overlaps and ensure valid concatenation even with prefix/suffix relationships.