algoadvance

Leetcode 520. Detect Capital

Problem Statement

The problem “520. Detect Capital” from LeetCode is defined as follows:

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

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

Otherwise, we define that this word doesn’t use capitals in a right way.

Example 1:

Input: "USA"
Output: True

Example 2:

Input: "FlaG"
Output: False

Clarifying Questions

  1. Q: Can the input string be empty? A: No, the input string will contain at least one letter.

  2. Q: Will the input string contain non-alphabetic characters? A: No, the input string will only contain alphabetic characters.

  3. Q: Is the input string limited to a specific length? A: The problem constraints do not specify a maximum length, but typical constraints apply (< 1000 characters).

Strategy

To solve this problem, we need to check the given string against the specified capitalization conditions:

  1. All characters are uppercase.
  2. All characters are lowercase.
  3. Only the first character is uppercase, and the rest are lowercase.

We can implement a function that checks these conditions in sequence.

Code

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    bool detectCapitalUse(string word) {
        // Check if all characters are uppercase
        if (all_of(word.begin(), word.end(), ::isupper)) {
            return true;
        }

        // Check if all characters are lowercase
        if (all_of(word.begin(), word.end(), ::islower)) {
            return true;
        }

        // Check if only the first character is uppercase and the rest are lowercase
        if (isupper(word[0]) && all_of(word.begin() + 1, word.end(), ::islower)) {
            return true;
        }

        // If none of the conditions are met, return false
        return false;
    }
};

int main() {
    Solution sol;
    
    // Test cases
    cout << boolalpha;  // Print boolean values as true/false instead of 1/0
    cout << sol.detectCapitalUse("USA") << endl;         // true
    cout << sol.detectCapitalUse("leetcode") << endl;    // true
    cout << sol.detectCapitalUse("Google") << endl;      // true
    cout << sol.detectCapitalUse("FlaG") << endl;        // false
    cout << sol.detectCapitalUse("g") << endl;           // true
    cout << sol.detectCapitalUse("A") << endl;           // true
    cout << sol.detectCapitalUse("uSa") << endl;         // false

    return 0;
}

Strategy Explained

  1. Check All Uppercase:
    • Use the all_of algorithm to determine if all characters in the string are uppercase.
  2. Check All Lowercase:
    • Similarly, use the all_of algorithm to check if all characters are lowercase.
  3. Check Capitalized Form:
    • Check if the first character is uppercase and the remainder of the string is lowercase using iteration and all_of.

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

Time Complexity

The time complexity of this solution is ( O(n) ) where ( n ) is the length of the input string. This is because each all_of call runs in linear time relative to the number of characters in the string. There are at most three sequential calls, making the overall complexity linear.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI