Problem Description

You need to determine if a word uses capital letters correctly. A word has correct capitalization if it follows one of these three patterns:

1. All uppercase: Every letter in the word is a capital letter (like "USA")
2. All lowercase: Every letter in the word is a lowercase letter (like "leetcode")
3. Title case: Only the first letter is capital and all other letters are lowercase (like "Google")

Given a string word, return true if the capitalization follows one of these valid patterns, otherwise return false.

The solution counts the total number of uppercase letters in the word using sum(c.isupper() for c in word). Then it checks if this count matches one of the valid patterns:

• Count is 0 (all lowercase)
• Count equals the word length (all uppercase)
• Count is 1 AND the first character is uppercase (title case)

If any of these conditions is met, the function returns true, otherwise false.

Intuition

The key insight is that we can determine if a word has valid capitalization by simply counting how many uppercase letters it contains. Instead of checking each character's position and case individually, we can use the count to identify which pattern the word follows.

Think about what makes each valid pattern unique:

• If a word is all lowercase, it has exactly 0 uppercase letters
• If a word is all uppercase, the number of uppercase letters equals the word's length
• If a word is in title case, it has exactly 1 uppercase letter, and that letter must be at position 0

This observation leads us to a clean solution: count the uppercase letters first, then check if the count matches any of our three valid patterns. The beauty of this approach is that we reduce the problem from pattern matching to simple counting and arithmetic comparisons.

For the title case check, we need an additional condition - not only should there be exactly one uppercase letter, but it must also be the first character. This prevents words like "leeTcode" from being incorrectly validated.

By using cnt == 0 or cnt == len(word) or (cnt == 1 and word[0].isupper()), we elegantly cover all three valid cases in a single return statement.

Solution Approach

The implementation follows a straightforward counting strategy:

1. Count uppercase letters: We iterate through each character in the word and count how many are uppercase using sum(c.isupper() for c in word). This gives us the total count cnt of uppercase letters in the string.

2. Check valid patterns: We then verify if the count matches any of the three valid capitalization patterns:

   • cnt == 0: This means all letters are lowercase (no uppercase letters found)
   • cnt == len(word): This means all letters are uppercase (every character counted as uppercase)
   • cnt == 1 and word[0].isupper(): This means exactly one uppercase letter exists AND it's the first character (title case)

The solution combines these checks using the logical OR operator, returning True if any condition is satisfied:

return cnt == 0 or cnt == len(word) or (cnt == 1 and word[0].isupper())

The time complexity is O(n) where n is the length of the word, as we need to traverse the string once to count uppercase letters. The space complexity is O(1) since we only use a single variable to store the count.

This approach is efficient because it makes only one pass through the string and uses simple arithmetic comparisons rather than complex pattern matching or regular expressions.

Example Walkthrough

Let's walk through the solution with the word "Google":

Step 1: Count uppercase letters

• Iterate through each character: 'G', 'o', 'o', 'g', 'l', 'e'
• Check if each is uppercase:
  • 'G' → uppercase ✓ (count = 1)
  • 'o' → lowercase (count = 1)
  • 'o' → lowercase (count = 1)
  • 'g' → lowercase (count = 1)
  • 'l' → lowercase (count = 1)
  • 'e' → lowercase (count = 1)
• Total uppercase count cnt = 1

Step 2: Check valid patterns

• Is cnt == 0? No (1 ≠ 0) - not all lowercase
• Is cnt == len(word)? No (1 ≠ 6) - not all uppercase
• Is cnt == 1 and word[0].isupper()?
  • cnt == 1? Yes ✓
  • word[0].isupper()? Yes, 'G' is uppercase ✓
  • Both conditions met → Title case pattern matched!

Result: Return true

Let's verify with an invalid example "FlaG":

• Count uppercase: 'F' (1), 'l' (1), 'a' (1), 'G' (2)
• Total cnt = 2
• Check patterns:
  • cnt == 0? No (2 ≠ 0)
  • cnt == len(word)? No (2 ≠ 4)
  • cnt == 1 and word[0].isupper()? No (2 ≠ 1)
• No pattern matched → Return false

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word. This is because the code iterates through each character in the string exactly once using the generator expression sum(c.isupper() for c in word) to count the number of uppercase letters. Each character check with isupper() takes O(1) time, and we perform this operation n times.

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variable cnt (an integer counter), regardless of the input size. The generator expression c.isupper() for c in word doesn't create a list but yields values one at a time, so it doesn't consume additional space proportional to the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Empty String Handling

The current solution doesn't explicitly handle empty strings. While Python's sum() would return 0 for an empty string and the comparison 0 == len("") would evaluate to True, making empty strings valid, this might not align with the problem's intent.

Solution: Add an explicit check for empty strings if they should be handled differently:

if not word:
    return True  # or False, depending on requirements

2. Non-Alphabetic Characters

The solution assumes the input contains only alphabetic characters. If the word contains numbers, spaces, or special characters, the logic might produce unexpected results. For example, "Hello123" would be considered valid title case even though it contains digits.

Solution: Either validate that the input contains only letters or clarify the expected behavior:

if not word.isalpha():
    return False  # Reject words with non-alphabetic characters

3. Single Character Words

For single-character words, the title case check (uppercase_count == 1 and word[0].isupper()) becomes redundant with the all-uppercase check. While this doesn't cause incorrect results, it can be confusing. A word like "I" satisfies both the all-uppercase pattern and the title case pattern.

Solution: Document this edge case or optimize the logic:

# For clarity, handle single characters separately
if len(word) == 1:
    return True  # Single characters are always valid

4. Performance with Generator vs List Comprehension

While the code uses sum(1 for char in word if char.isupper()) which is memory-efficient, some might mistakenly use sum([1 for char in word if char.isupper()]) with brackets, creating an unnecessary list in memory.

Solution: Stick with generator expressions for better memory efficiency:

# Good: Generator expression (memory efficient)
uppercase_count = sum(1 for char in word if char.isupper())

# Avoid: List comprehension (creates intermediate list)
uppercase_count = sum([1 for char in word if char.isupper()])

5. Mixed Case in the Middle

The most common mistake is not realizing that words like "LeetCode" or "iPhone" would be considered invalid by this solution. Developers might expect these to be valid, but they don't match any of the three patterns (they have uppercase letters that aren't just at the beginning or throughout).

Solution: Clearly document that mixed-case patterns are invalid, or modify the solution if such patterns should be accepted:

# If you need to accept camelCase or PascalCase:
def detectCapitalUse(self, word: str) -> bool:
    # Original three patterns
    if (uppercase_count == 0 or 
        uppercase_count == len(word) or 
        (uppercase_count == 1 and word[0].isupper())):
        return True
  
    # Additional pattern for camelCase if needed
    # (This would require different logic)
    return False