520. Detect Capital

EasyString

Problem Description

The problem at hand defines a correct capital usage in a word according to three rules:

All letters in the word are uppercase (for example, "USA").
All letters in the word are lowercase (for example, "leetcode").
Only the first letter in the word is uppercase (for example, "Google").

We are given a word and need to determine if the capitalization of the word follows any of the above rules. The function should return true if the word's usage of capitals is right and false otherwise.

Intuition

The solution is based on the observation that we can only have three correct capitalization scenarios. The approach involves counting the number of uppercase characters in the word and then applying conditional logic based on the count obtained. The reasoning process is as follows:

Count the number of uppercase letters in the word.
Determine if the number of uppercase letters equals the length of the word, which means all characters are uppercase.
Check if there are no uppercase letters, which means all are lowercase.
The final condition is if there's only one uppercase letter which also has to be the first character.

If any of these conditions are met, the capital usage is correct, and thus we should return true. Otherwise, the usage doesn't match any of the correct forms, and we should return false.

Solution Approach

The provided Python code for the solution follows a straightforward approach using basic programming constructs. The steps of the implementation are:

Initialize a variable cnt to 0 to keep track of the number of uppercase characters in the word.
Iterate through each character c in the given word.
For each character, use the isupper() method which is a string method in Python that returns True if all cased characters in the string are uppercase and there is at least one cased character, otherwise, it returns False.
If c.isupper() is True, increment the cnt by 1.
After the loop, we have three conditions to check, corresponding to the right usage of capitals:
- If cnt is 0, this means there are no uppercase letters, and all letters are lowercase.
- If cnt equals the length of the word, this means all letters in the word are uppercase.
- If cnt is 1 and the first character of the word word[0].isupper() is True, this means only the first letter is uppercase.

If any of these three conditions are True, the function returns True, indicating the capital usage in the word is right. Otherwise, it returns False.

The algorithm primarily relies on character inspection and condition checking, without the need for any special data structures or complex patterns. It is an example of a linear scan through the input, with a constant-time check performed at each step.

In terms of time complexity, this approach operates in O(n) time, where n is the length of the word since it requires a single pass through all the letters of the word.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the word "FlaG" to demonstrate how the solution approach works step by step.

We start with cnt = 0 because we haven't counted any uppercase characters yet.
We iterate through each character in the word "FlaG".
- 'F' is uppercase, cnt becomes 1.
- 'l' is lowercase, cnt remains 1.
- 'a' is lowercase, cnt remains 1.
- 'G' is uppercase, cnt becomes 2.
Now the iteration is complete and we have cnt = 2 for the word which has a length of 4 characters.
We go through the three conditions to check whether the capital usage is correct.
- cnt is not 0, so we cannot say all letters are lowercase.
- cnt does not equal the length of the word (2 != 4), so we cannot say all letters are uppercase.
- cnt is not 1, so we cannot say only the first letter is uppercase. Additionally, even if cnt were 1, the uppercase letter has to be the first character, which is not the only uppercase character in our case.

Since none of the conditions for correct capital usage are met, the function should return False for the word "FlaG". The capitalization of this word doesn't adhere to any of the three described rules.

Solution Implementation

1class Solution:
2    def detectCapitalUse(self, word: str) -> bool:
3        # Initialize a counter for uppercase letters
4        uppercase_count = 0
5      
6        # Loop through each character in the word
7        for char in word:
8            # If the character is uppercase, increment the count
9            if char.isupper():
10                uppercase_count += 1
11              
12        # Check the conditions for correct capital usage:
13        # 1. No uppercase letters in the word
14        # 2. All characters in word are uppercase
15        # 3. Only the first character in word is uppercase
16        return (uppercase_count == 0 or
17                uppercase_count == len(word) or
18                (uppercase_count == 1 and word[0].isupper()))
19

1class Solution {
2    public boolean detectCapitalUse(String word) {
3        int capitalLetterCount = 0; // Initialize count of capital letters to 0.
4
5        // Loop through each character in the string.
6        for (char character : word.toCharArray()) {
7            // Increase the count if the current character is uppercase.
8            if (Character.isUpperCase(character)) {
9                capitalLetterCount++;
10            }
11        }
12
13        // Check if the word is all lowercase, all uppercase, or capitalized properly.
14        // A word is capitalized properly if it either (1) has no capital letters,
15        // (2) is entirely capital letters, or (3) has the first letter as a capital 
16        // letter followed by all lowercase letters.
17        return capitalLetterCount == 0 // No capital letters.
18            || capitalLetterCount == word.length() // All letters are uppercase.
19            || (capitalLetterCount == 1 && Character.isUpperCase(word.charAt(0))); // Only the first letter is uppercase.
20    }
21}
22

1class Solution {
2public:
3    bool detectCapitalUse(string word) {
4        int capitalCount = 0; // Initialize a counter for capital letters
5      
6        // Iterate through each character in the word
7        for (char c : word) {
8            // If the character is an uppercase letter, increment the counter
9            if (isupper(c)) {
10                ++capitalCount;
11            }
12        }
13      
14        // Check the capital usage rules:
15        // 1. No capital letters in the word
16        // 2. All letters are capital letters
17        // 3. Only the first letter is capital
18        bool allCapitals = capitalCount == word.size(); // All letters are capitals
19        bool noCapitals = capitalCount == 0;            // No letters are capitals
20        bool firstCapitalOnly = capitalCount == 1 && isupper(word[0]); // Only the first letter is capital
21      
22        // Return true if any of the conditions above are met
23        return allCapitals || noCapitals || firstCapitalOnly;
24    }
25};
26

1/**
2 * Checks if a given word uses capital letters correctly.
3 * Correct use of capitals is defined by either all letters being capitals,
4 * no letter being capital, or only the first letter being capital.
5 * 
6 * @param {string} word - The word to check for correct capital use.
7 * @returns {boolean} - True if the word uses capitals correctly, false otherwise.
8 */
9function detectCapitalUse(word: string): boolean {
10    // Initialize a counter for capital letters.
11    let capitalCount = 0;
12  
13    // Iterate through each character in the word.
14    for (let i = 0; i < word.length; i++) {
15        // If the character is an uppercase letter, increment the counter.
16        if (word[i] >= 'A' && word[i] <= 'Z') {
17            capitalCount++;
18        }
19    }
20  
21    // Check the capital usage rules.
22    const allCapitals = capitalCount === word.length; // All letters are capitals.
23    const noCapitals = capitalCount === 0; // No letters are capitals.
24    const firstCapitalOnly = capitalCount === 1 && word[0] >= 'A' && word[0] <= 'Z'; // Only the first letter is capital.
25  
26    // Return true if any of the conditions above are met.
27    return allCapitals || noCapitals || firstCapitalOnly;
28}
29

Time and Space Complexity

The given Python code is designed to determine whether a word uses capitals correctly according to the following rules:

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

The time complexity and space complexity of the code are as follows:

Time Complexity

The time complexity of the function is O(n) where n is the length of the input string word. This is because the function goes through each character in the string exactly once to count how many uppercase letters are present.

Space Complexity

The space complexity of the code is O(1) since a fixed amount of extra space is used regardless of the input size. The extra space comes from the variable cnt, which is used to count the number of uppercase characters in the string. No additional space that grows with the input size is used.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know