Jobs

Interviews

Discussions

Detect Capital

#1054 Most AskedEasy

Detect Capital #1054 Most Asked

Easy

Microsoft

9 views

Topics:

Strings

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like "USA".
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital, like "Google".

Given a string word, return true if the usage of capitals in it is right.

Example 1:

Input: word = "USA"
Output: true

Example 2:

Input: word = "FlaG"
Output: false

Constraints:

1 <= word.length <= 100
word consists of lowercase and uppercase English letters.

Try coding it in LeetCode

Detect Capital

#1054 Most AskedEasy

Detect Capital #1054 Most Asked

Easy

Microsoft

9 views

Topics:

Strings

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like "USA".
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital, like "Google".

Given a string word, return true if the usage of capitals in it is right.

Example 1:

Input: word = "USA"
Output: true

Example 2:

Input: word = "FlaG"
Output: false

Constraints:

1 <= word.length <= 100
word consists of lowercase and uppercase English letters.

Try coding it in LeetCode

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:

Can the input string contain characters other than uppercase and lowercase English letters?
Is an empty string a valid input? If so, should it return true or false?
Are there any specific length limitations on the input string?
Is it case-sensitive? For example, should a string like 'FlaG' return false?
Can I assume the input string will always be valid (e.g., no null characters)?
What happens if I receive a string like '123'? Should that return true or false?

Brute Force Solution

Approach

The brute force approach to this problem involves checking every possible capitalization pattern of a word. We will consider all upper and lowercase variations to determine if the word adheres to the defined capital usage rules. Essentially, we check every single possibility.

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

First, check if all the letters in the word are uppercase.
Next, check if all the letters in the word are lowercase.
Then, check if only the first letter of the word is uppercase and the rest are lowercase.
If any of these three conditions are true, the word uses capital letters correctly.
If none of these are true, the word does not follow the rules.

Code Implementation

def detect_capital_use(word):
    # Check if all letters are uppercase
    if word.isupper():
        return True

    # Check if all letters are lowercase
    if word.islower():
        return True

    # Check if only the first letter is uppercase
    if len(word) > 0 and word[0].isupper():

        # Iterate through the remaining letters to ensure they are lowercase
        for index in range(1, len(word)):
            if word[index].isupper():
                return False
        return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs at most three iterations over the word. The first iteration checks if all letters are uppercase, the second checks if all letters are lowercase, and the third checks if only the first letter is uppercase. Each of these checks iterates through the word once, so the maximum number of iterations is a constant multiple of the word's length, n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The brute force approach checks the capitalization of a word by iterating through it. No auxiliary data structures like arrays, lists, or hash maps are created. The algorithm only uses a few constant-size variables for loop counters and boolean flags to indicate if the word is all uppercase, all lowercase, or capitalized. Therefore, the space complexity is constant, independent of the word's length, N.

Optimal Solution

Approach

The most efficient approach is to check the input word against a small number of possible valid capitalizations. We can decide if the word is valid very quickly this way. The problem constraints allow us to check only 3 conditions.

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

First, determine the length of the given word.
Check if all letters are uppercase. If they are, the word is valid.
Check if all letters are lowercase. If they are, the word is valid.
Check if only the first letter is uppercase and the rest are lowercase. If so, the word is valid.
If none of the above conditions are met, the word is invalid.

Code Implementation

def detect_capital_use(word):
    word_length = len(word)

    #Check if all letters are uppercase
    if word.isupper():
        return True

    #Check if all letters are lowercase
    if word.islower():
        return True

    #Check if only the first letter is uppercase
    if word_length > 0 and word[0].isupper():
        # Need to check the rest of the word is lowercase
        if word[1:].islower():
            return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm checks a word of length n against a fixed number of conditions: all uppercase, all lowercase, and first letter uppercase with the rest lowercase. Each of these checks iterates through the word at most once. Therefore, the time complexity is proportional to the length of the word, n, resulting in O(n).

Space Complexity

O(1) – The algorithm checks a few conditions without using any extra data structures that scale with the input word's length, N. No additional lists, hash maps, or other memory-intensive components are created. Only a few boolean variables are used to track the capitalization checks. Therefore, the space complexity is constant regardless of the input size, N.

Edge Cases

Case	How to Handle
Null or empty string	Return True immediately since an empty string technically satisfies the condition (vacuously true).
String with a single character	Return True as a single character string is considered to be all uppercase or all lowercase.
String with mixed case in the middle of the word	Return False, as this doesn't follow any capitalization rule.
String with numbers or special characters	Ignore non-alphabetic characters when checking case, only looking at the alphabetic characters within the string.
Very long string (potential performance issue)	The solution should iterate through the string once, so performance is O(n) and scales linearly with the string length.
String with all lowercase letters	Return True as this meets the condition of all lowercase.
String with all uppercase letters	Return True as this meets the condition of all uppercase.
String with only the first letter capitalized	Return True because the input matches the first letter capitalized format.

Null or empty string

How to Handle:

Return True immediately since an empty string technically satisfies the condition (vacuously true).

String with a single character

How to Handle:

Return True as a single character string is considered to be all uppercase or all lowercase.

String with mixed case in the middle of the word

How to Handle:

Return False, as this doesn't follow any capitalization rule.

String with numbers or special characters

How to Handle:

Ignore non-alphabetic characters when checking case, only looking at the alphabetic characters within the string.

Very long string (potential performance issue)

How to Handle:

The solution should iterate through the string once, so performance is O(n) and scales linearly with the string length.

String with all lowercase letters

How to Handle:

Return True as this meets the condition of all lowercase.

String with all uppercase letters

How to Handle:

Return True as this meets the condition of all uppercase.

String with only the first letter capitalized

How to Handle:

Return True because the input matches the first letter capitalized format.

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:

Can the input string contain characters other than uppercase and lowercase English letters?
Is an empty string a valid input? If so, should it return true or false?
Are there any specific length limitations on the input string?
Is it case-sensitive? For example, should a string like 'FlaG' return false?
Can I assume the input string will always be valid (e.g., no null characters)?
What happens if I receive a string like '123'? Should that return true or false?

Brute Force Solution

Approach

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

First, check if all the letters in the word are uppercase.
Next, check if all the letters in the word are lowercase.
Then, check if only the first letter of the word is uppercase and the rest are lowercase.
If any of these three conditions are true, the word uses capital letters correctly.
If none of these are true, the word does not follow the rules.

Code Implementation

def detect_capital_use(word):
    # Check if all letters are uppercase
    if word.isupper():
        return True

    # Check if all letters are lowercase
    if word.islower():
        return True

    # Check if only the first letter is uppercase
    if len(word) > 0 and word[0].isupper():

        # Iterate through the remaining letters to ensure they are lowercase
        for index in range(1, len(word)):
            if word[index].isupper():
                return False
        return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, determine the length of the given word.
Check if all letters are uppercase. If they are, the word is valid.
Check if all letters are lowercase. If they are, the word is valid.
Check if only the first letter is uppercase and the rest are lowercase. If so, the word is valid.
If none of the above conditions are met, the word is invalid.

Code Implementation

def detect_capital_use(word):
    word_length = len(word)

    #Check if all letters are uppercase
    if word.isupper():
        return True

    #Check if all letters are lowercase
    if word.islower():
        return True

    #Check if only the first letter is uppercase
    if word_length > 0 and word[0].isupper():
        # Need to check the rest of the word is lowercase
        if word[1:].islower():
            return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string	Return True immediately since an empty string technically satisfies the condition (vacuously true).
String with a single character	Return True as a single character string is considered to be all uppercase or all lowercase.
String with mixed case in the middle of the word	Return False, as this doesn't follow any capitalization rule.
String with numbers or special characters	Ignore non-alphabetic characters when checking case, only looking at the alphabetic characters within the string.
Very long string (potential performance issue)	The solution should iterate through the string once, so performance is O(n) and scales linearly with the string length.
String with all lowercase letters	Return True as this meets the condition of all lowercase.
String with all uppercase letters	Return True as this meets the condition of all uppercase.
String with only the first letter capitalized	Return True because the input matches the first letter capitalized format.

Null or empty string

How to Handle:

Return True immediately since an empty string technically satisfies the condition (vacuously true).

String with a single character

How to Handle:

Return True as a single character string is considered to be all uppercase or all lowercase.

String with mixed case in the middle of the word

How to Handle:

Return False, as this doesn't follow any capitalization rule.

String with numbers or special characters

How to Handle:

Ignore non-alphabetic characters when checking case, only looking at the alphabetic characters within the string.

Very long string (potential performance issue)

How to Handle:

The solution should iterate through the string once, so performance is O(n) and scales linearly with the string length.

String with all lowercase letters

How to Handle:

Return True as this meets the condition of all lowercase.

String with all uppercase letters

How to Handle:

Return True as this meets the condition of all uppercase.

String with only the first letter capitalized

How to Handle:

Return True because the input matches the first letter capitalized format.

0/1114 Microsoft questions completed

0/1114 completed