algoadvance

The problem “520. Detect Capital” on LeetCode requires us to implement a function that determines if the usage of capitals in a given word is correct. Specifically, the usage of capitals in a word is considered correct if one of the following conditions is met:

1. All letters in the word are capitals, e.g., “USA”.
2. All letters in the word are not capitals, e.g., “leetcode”.
3. Only the first letter in the word is capitalized, e.g., “Google”.

Given a single word as a string, we need to return True if the word follows any of the above capitalization rules and False otherwise.

Clarifying Questions

1. Input Constraints: Is the word guaranteed to be non-empty and consist only of English letters (both uppercase and lowercase)?
   • Yes, the problem usually guarantees this.
2. Case Sensitivity: Are we guaranteed that the input will only contain letter characters, and should the check be case-sensitive?
   • Yes, case-sensitivity is a fundamental part of the problem.

Strategy

To solve this problem, we can consider the following steps:

1. Case 1: All letters are uppercase: Check if the entire string is equal to its uppercase version.
2. Case 2: All letters are lowercase: Check if the entire string is equal to its lowercase version.
3. Case 3: Only the first letter is uppercase, and the rest are lowercase: Check if the first letter is uppercase and the substring starting from the second letter is all lowercase.

Using these conditions, we can determine whether the word’s capitalization is correct or not.

Code

Here’s the Python code to solve this problem:

def detectCapitalUse(word: str) -> bool:
    if word.isupper():
        return True
    if word.islower():
        return True
    if word[0].isupper() and word[1:].islower():
        return True
    return False

Time Complexity

The time complexity of the solution is O(n), where n is the length of the given word. This is because:

• The isupper() method checks each character to ensure it’s uppercase, taking O(n) time.
• The islower() method checks each character to ensure it’s lowercase, taking O(n) time.
• The slicing operation word[1:] takes O(n) time to create the slice, but the combined checks still result in linear time complexity.

Thus, the implementation effectively travels over the word at most three times, resulting in a time complexity of O(n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?