Detect Capital
EasyPrompt
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: trueExample 2:
Input: word = "FlaG"
Output: false
Constraints:
1 <= word.length <= 100wordconsists of lowercase and uppercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the three valid capitalization rules by creating modified versions of the input string (all uppercase, all lowercase, title case) and comparing them with the original word.
Algorithm
- Check if the
wordis equal to its all-uppercase version (word.toUpperCase()). - Check if the
wordis equal to its all-lowercase version (word.toLowerCase()). - Construct a "Title Case" version of the word by capitalizing the first letter and making the rest lowercase. Check if the
wordis equal to this new string. - If any of the above three checks pass, the usage is correct, so return
true. - If all checks fail, return
false.
Walkthrough
The core idea is to check if the input word matches any of the three allowed formats. We can generate a string for each valid format based on the input word and then perform a string comparison.
- All Caps: Check if
word.equals(word.toUpperCase()). - All Lowercase: Check if
word.equals(word.toLowerCase()). - Title Case: Check if
wordis equal to its title-cased version. This is constructed by taking the first character, making it uppercase, and appending the rest of the string in lowercase.
If any of these conditions are true, the word's capitalization is correct.
class Solution { public boolean detectCapitalUse(String word) { if (word.length() <= 1) { return true; } // Case 1: All letters are capitals boolean allCaps = word.equals(word.toUpperCase()); // Case 2: All letters are not capitals boolean allLower = word.equals(word.toLowerCase()); // Case 3: Only the first letter is capital String titleCase = word.substring(0, 1).toUpperCase() + word.substring(1).toLowerCase(); boolean isTitleCase = word.equals(titleCase); return allCaps || allLower || isTitleCase; }}Complexity
Time
O(n), where n is the length of the word. Each string operation (`toUpperCase`, `toLowerCase`, `substring`, `equals`) takes O(n) time. We perform a constant number of these operations.
Space
O(n), where n is the length of the word. This is due to the creation of new strings to hold the uppercase, lowercase, and title-case versions of the word for comparison.
Trade-offs
Pros
Very simple and easy to understand.
Leverages built-in string functions, leading to concise code.
Cons
Inefficient in terms of memory usage as it creates several new temporary strings.
Can be slower than manual iteration due to the overhead of creating and comparing entire strings.
This approach iterates through the word once to count the total number of capital letters. Based on this count and the status of the first letter, it determines if the capitalization is valid.
Algorithm
- Initialize a counter
capitalCountto 0. - Loop through each character of the
word. - Inside the loop, if the character is uppercase (e.g., using
Character.isUpperCase()), incrementcapitalCount. - After the loop, evaluate the final count:
- If
capitalCountis 0 (all lowercase) orcapitalCountis equal to the word's length (all caps), returntrue. - If
capitalCountis 1 AND the first character of the word is uppercase, returntrue. - Otherwise, return
false.
- If
Walkthrough
Instead of creating new strings, we can analyze the properties of the existing string. The number of capital letters provides a strong signal about which rule might apply. We iterate through the word and maintain a count of uppercase letters.
Let n be the length of the word and capitalCount be the number of uppercase letters. The three rules can be translated as:
- All Caps:
capitalCount == n. - All Lowercase:
capitalCount == 0. - Title Case:
capitalCount == 1and the first letter is uppercase.
class Solution { public boolean detectCapitalUse(String word) { int n = word.length(); if (n <= 1) { return true; } int capitalCount = 0; for (int i = 0; i < n; i++) { if (Character.isUpperCase(word.charAt(i))) { capitalCount++; } } if (capitalCount == 0 || capitalCount == n) { return true; } if (capitalCount == 1 && Character.isUpperCase(word.charAt(0))) { return true; } return false; }}Complexity
Time
O(n), where n is the length of the word. We perform a single pass through the string.
Space
O(1). We only use a few extra variables for the count and loop index, regardless of the input string's size.
Trade-offs
Pros
Much more memory efficient than the string manipulation approach.
Still relatively simple to implement and understand.
Cons
It always iterates through the entire string, even if the word is clearly invalid early on (e.g., "fLaG").
This is the most efficient approach. It involves a single pass through the string, checking for adherence to the capitalization rules. It can exit early as soon as a rule is violated, making it faster on average.
Algorithm
- If the word length is 1 or less, return
true. - Check the case of the first two characters.
- Case A: First and second characters are uppercase. This implies the "All Caps" rule. Iterate from the third character to the end. If any character is lowercase, return
false. - Case B: All other combinations. This covers "All Lowercase" and "Title Case". In both scenarios, all characters from the second one onwards must be lowercase. Iterate from the second character to the end. If any character is uppercase, return
false. - If the loops complete without returning
false, it means the word is valid. Returntrue.
Walkthrough
This method directly checks if the characters in the word follow one of the three allowed patterns. The logic is based on the case of the first one or two characters, which determines the expected pattern for the rest of the string. This allows for early termination if a rule is broken.
For example, if the word is "FlaG", we see 'F' (uppercase) and 'l' (lowercase). This means the word must be in "Title Case" format, so all subsequent characters must be lowercase. When we encounter 'G' at index 3, we know the rule is violated and can immediately return false without checking the rest of the string.
class Solution { public boolean detectCapitalUse(String word) { int n = word.length(); if (n <= 1) { return true; } boolean firstCharIsUpper = Character.isUpperCase(word.charAt(0)); boolean secondCharIsUpper = Character.isUpperCase(word.charAt(1)); if (firstCharIsUpper && secondCharIsUpper) { // Rule: All caps ("USA") // The rest of the characters must be uppercase. for (int i = 2; i < n; i++) { if (Character.isLowerCase(word.charAt(i))) { return false; } } } else { // Rule: All lower ("leetcode") or Title Case ("Google") // In both cases, the rest of the characters must be lowercase. for (int i = 1; i < n; i++) { if (Character.isUpperCase(word.charAt(i))) { return false; } } } return true; }}Complexity
Time
O(n), where n is the length of the word. In the worst case, it iterates through the entire string once. In the best/average case for invalid strings, it can be faster.
Space
O(1). No extra space proportional to the input size is used.
Trade-offs
Pros
Most efficient in terms of both time and space.
Can terminate early if an invalid pattern is found, leading to better average-case performance.
Optimal O(1) space complexity.
Cons
The logic can be slightly more complex to write compared to the other approaches due to the conditional branching.
Solutions
Solution
class Solution {public: bool detectCapitalUse(string word) { int cnt = 0; for (char c : word) if (isupper(c)) ++cnt; return cnt == 0 || cnt == word.size() || (cnt == 1 && isupper(word[0])); }};class Solution: def detectCapitalUse(self, word: str) -> bool: cnt = 0 for c in word: if c . isupper(): cnt += 1 return cnt == 0 or cnt == len(word) or (cnt == 1 and word[0]. isupper())class Solution {public boolean detectCapitalUse(String word) { int cnt = 0; for (char c : word.toCharArray()) { if (Character.isUpperCase(c)) { ++cnt; } } return cnt == 0 || cnt == word.length() || (cnt == 1 && Character.isUpperCase(word.charAt(0))); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.