Detect Capital | LeetCode Problems And Solution

Detect Capital is an easy LeetCode string problem, but it is a nice test of how carefully you turn a set of English rules into code. You are given a word and have to decide whether its capital letters are used "properly". There are only three allowed shapes, and the whole problem is about checking those shapes without writing a tangle of if-else blocks.

It is also a good reminder to test your own code on every rule. The older solution on this page passed "USA" but failed plain lowercase words, which shows how easy it is to check one example and move on.

Problem

You get one word made only of English letters, upper or lower case. Return true if the capitals in the word follow one of these three patterns, and false otherwise:

• Every letter is a capital, like USA.
• No letter is a capital, like leetcode.
• Only the first letter is a capital and the rest are small, like Google.

Input: a non-empty string word.

Output: a boolean, true if the usage is correct.

Constraints: the word is not empty and contains only uppercase and lowercase Latin letters. (On LeetCode today the length goes up to 100.)

Input: word = "USA"
Output: true

Input: word = "FlaG"
Output: false

Approach

Instead of checking each rule separately with its own loop, notice that all three rules can be described by one number: how many capital letters the word has. Call it upper and let n be the length.

1. Count the capital letters in one pass.
2. If upper == 0, the word is all small letters. Valid.
3. If upper == n, the word is all capitals. Valid.
4. If upper == 1 and that capital is the first character, it is the "Google" shape. Valid.
5. Anything else has a capital in the wrong place. Invalid.

Why does the count work for rule 3? If there is exactly one capital and the first letter is a capital, then that single capital must be the first letter, so every other letter is small. No second loop needed.

Dry run with "FlaG": the capitals are F and G, so upper = 2 and n = 4. It is not 0, not 4 and not 1, so the answer is false.

Dry run with "USA": upper = 3 and n = 3, so the all-capitals rule matches and the answer is true.

Solution in Java

The previous version of this post first checked word.equals(word.toUpperCase()), which is fine for "USA". After that its loop condition was c <= 'A' && c >= 'Z', which can never be true (no character is both at most 'A' and at least 'Z'), and the method then returned false. So "leetcode" and "Google" were both reported as wrong. The version below fixes that with the counting idea.

class Solution {
    public boolean detectCapitalUse(String word) {
        int upper = 0;
        for (int i = 0; i < word.length(); i++) {
            if (Character.isUpperCase(word.charAt(i))) {
                upper++;
            }
        }
        int n = word.length();
        // Rule 1: no capitals at all          -> "leetcode"
        // Rule 2: every letter is a capital    -> "USA"
        // Rule 3: exactly one capital, and it is the first letter -> "Google"
        return upper == 0
            || upper == n
            || (upper == 1 && Character.isUpperCase(word.charAt(0)));
    }

    // Small driver for local testing (LeetCode only needs the method above)
    public static void main(String[] args) {
        Solution s = new Solution();
        String[] tests = {"USA", "FlaG", "leetcode", "Google", "g", "G", "gOOGLE", "ABc"};
        for (String t : tests) {
            System.out.println(t + " -> " + s.detectCapitalUse(t));
        }
    }
}

On LeetCode you only submit the detectCapitalUse method. The main method is there so you can run it locally. I tested the two samples plus single-letter words ("g" and "G", both valid), a word with every letter capital except the first ("gOOGLE", invalid), and one that ends with a small letter after capitals ("ABc", invalid).

Output

USA -> true
FlaG -> false
leetcode -> true
Google -> true
g -> true
G -> true
gOOGLE -> false
ABc -> false

For the two official samples, that is true for "USA" and false for "FlaG".

Complexity

Time: O(n), one pass over the word to count capitals.

Space: O(1). We only keep a counter. Compare that with the toUpperCase() trick, which builds a whole new string of length n just to compare it.

Common mistakes

• Comparing characters with ranges written backwards, like c <= 'A' && c >= 'Z'. It should be c >= 'A' && c <= 'Z', or simply Character.isUpperCase(c).
• Forgetting the one-letter case. "G" and "g" are both valid, and the counting method handles them without a special branch.
• Only checking the first letter and the second letter. "FLaG" has a capital second letter but is still invalid, because the pattern breaks later. The count catches this.
• Using a regex like [A-Z]*|[a-z]*|[A-Z][a-z]* is short and correct, but in an interview, be ready to explain why it is slower than a single counting loop.

More easy LeetCode practice on the site: Shuffle String and Find Lucky Integer in an Array.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More LeetCode solutions All coding problems MCQ practice