[Google Interview] Detect Capital – Be on the Right Side of Change

[toc]

Company Tag: Google

Problem Formulation

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

Rule 1: All letters in this word are capitals, like “USA”.
Rule 2: All letters in this word are not capitals, like “welcome”.
Rule 3: 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.

Constraints:

1 <= word.length <= 100
The word can consist of lowercase and uppercase English letters.

Examples

Let’s have a look at some examples to improve our understanding of this problem.

Example 1:
Input: word = “USA”
Output: True
Explanation: All letters are in Uppercase. #Rule 1 is followed in this example.

Example 2:
Input: word = “FlaG”
Output: False
Explanation: The first and last letters are in Uppercase, which does not follow the rules defined for correct usage of capitals in the given word.

Example 3:
Input: word = “Finxter”
Output: True
Explanation: Only first letter is in Uppercase. #Rule 3 is followed in this example.

Example 4:
Input: word = “welcome”
Output: True
Explanation: None of the letters are in Uppercase. #Rule 2 is followed in this example.

Example 5:
Input: word = “hELLO”
Output: False
Explanation: None of the rules is followed in this example.

Now that you have a clear understanding of the problem let’s dive into the ways to solve this question.

Method 1: Using isupper()

Approach: The basic idea of this method is to use the built-in Python method, i.e., isupper() to check if a letter in the given word is in uppercase or not. Them, you will need the help of a counter variable that keeps the count of the number of upper case letters present in the given word. Let’s dissect the rule that must be followed based on the count of uppercase letters present in the word:

If the number of uppercase letters in the word is equal to the length of the given word, then it satisfies Rule 1.
If the number of uppercase letters in the word is zero, then it satisfies Rule 2.
If the given word has only one uppercase letter such that this uppercase letter is at the index zero, then it satisfies Rule 3.

Follow the diagram given below that demonstrates the approach mentioned above with the help of visual examples:

Python’s isupper() method:
The isupper() method is used in Python to check if all the characters are in uppercase. It returns True if the characters are uppercase; otherwise, it returns False. Only the alphabet characters are checked using this method.

Syntax: string.isupper()

Algorithm:

Initialize the variable “c” which will store the number of capital letters in the given word.
Increment the value of variable c every time a letter is in uppercase.
Check the count of c. For the usage of capitals in a word to be right, the cases are:
- If c is equal to 0, then all the letters are lowercase hence, return True.
- If c is equal to len(word), then all the letters are uppercase hence, return True.
- If c is equal to 1 and only the first letter is capital, return True.
- Return False if none of the above-mentioned conditions is satisfied.

Solution:

def detect_capital(word):
    c = 0
    for letter in word:
        if letter.isupper():
            c = c + 1
    if c == 0 or c == len(word):
        return True
    if c == 1 and word[0].isupper():
        return True
    return False

Test Case Analysis: Let’s run this solution on our examples.

# Example 1
word = “USA”
print(detect_capital(word))
# True

# Example 2
word = “FlaG”
print(detect_capital(word))
# False

# Example 3
word = “Finxter”
print(detect_capital(word))
# True

# Example 4
word = “welcome”
print(detect_capital(word))
# True

# Example 5
word = “hELLO”
print(detect_capital(word))
# False

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: The time complexity of this method is O(n) as you have traverse the entire string only once.
Space Complexity: The space complexity of this method is O(1) since no extra space has been used.

Method 2: Using Regular Expressions

Approach: The regex module is an extremely powerful tool used in Python that helps you to solve complex problems with ease. In this approach, you just have to use the three regular expressions that match each of the valid formats / rules of the string.

All the letters in uppercase: ^[ A – Z]* $
All the letters in lowercase: ^[ a – z]* $
Only first letter in uppercase: ^[A – Z][a – z]$
- This regular expression means that the first letter is uppercase. An advanced version of this regular expression is ^([A-Z][a-z] )?[A-Z][a-z]$
Note: Always use ^ for the start of the string and $ for the end of the string.

Re.match() in Python:
The re.match() method in Python will look through the passed regular expression and return the first occurrence. The re.match() method checks for a match just at the start of the string. In this way, if a match is found, it returns the match object. However, if a match is not found in the first line, it returns null.

Syntax: re.match(regular expression, string)

Recommended Read: Python Regex Match

Now let’s have a look at the solution:

import re
def detect_capital(word):
    if re.match("^[A-Z][a-z]*$|^[A-Z]*$|^[a-z]*$", word) == None:
        return False
    else:
        return True

Test Case Analysis: Let’s run this solution on our examples.

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: The time complexity of this method is O(n) as we have traversed the string only once.
Space Complexity: The space complexity of this method is O(1) as no extra space has been used.

Google, Facebook, and Amazon engineers are regular expression masters. If you want to become one as well, check out our new book: The Smartest Way to Learn Python Regex (Amazon Kindle/Print, opens in new tab).

Method 3: Using string.ascii_uppercase:

string.ascii_uppercase method:
The string.ascii_uppercase method is a constant defined within the string module in Python. It is used to return the following text string:’ABCDEFGHIJKLMNOPQRSTUVWXYZ’

Approach: The idea in this approach is to check if the letter is capital by using the ascii_uppercase method from the string. The logic is similar to the one that we followed in the first approach. Thus, you have to check if the letter belongs in this list (returned by ascii_uppercase). If yes, the letter is uppercase, hence increase the counter variable which keeps a count of the capital letters. Finally, return True if the length of c is 0 or equal to the length of the given word, or if the value stored within the counter variable is 1, and the first letter is capital. Else, return False.

Note: The purpose of this approach is to introduce you to the ascii_uppercase method.

Solution:

import string


def detect_capital(word):
    n = len(word)
    if not n:
        return True
    c = 0
    for letter in word:
        if letter in string.ascii_uppercase:
            c = c + 1
    if c in (0, n) or (c == 1 and word[0] in string.ascii_uppercase):
        return True
    return False

Test Case Analysis: Let’s run this solution on our examples.

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: The time complexity of this method is O(n) as we have traversed the string only once.
Space Complexity: The space complexity of this method is O(1) as no extra space has been used.

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

Recommended: Finxter Computer Science Academy

One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
So, do you want to master the art of web scraping using Python’s BeautifulSoup?
If the answer is yes – this course will take you from beginner to expert in Web Scraping.