Leetcode: 520. Detect Capital

Introduction

In this series of "Leetcode" posts I will publish solutions to leetcode problems. It is true that you can find most/lots of leetcode solutions on the web, but I will try to post my solutions to problems that are interesting or to problems for which the solutions out there are not well explained and deserve a better explanation.

The aim is to share knowledge, and that people who are studying, preparing for interviews, or just practicing, can become better at solving problems. Please feel free to comment if you have a suggestion or a different approach!

Problem statement

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:

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

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

Solution

This is quite an simple yet interesting problem. You can check the available solutions at leetcode. Here I am going to show another solution using a different approach.

First try

At first, after reading the problem statement and seeing the examples, it is easy to see that all the characters after the first one must be equal, the only problem is checking if the first character is Uppercase or Lowercase, and then, based on that information, check for the rest of the string.

That is to say:

1. If the string starts with an Uppercase, then either the rest of the string must also be Uppercase, or the rest of the string must in Lowercase.

2. If the string starts with a Lowercase, then the rest must be Lowercase as well.

That seems simple enough, and it should probably be done in one pass over the whole string, given a linear time complexity O(n).

Given this situation I was thinking in a general solution that would do one pass over the string and check some condition based on the first character.

This approach can get a bit confusing in the case the first letter is Uppercase (point number 1 mentioned above), as you would also need to check the second character to see if you need to check for all other characters to be Uppercase or lowercase.

At this point the solution may seem quite easy, but would require doing an if-else statement, with for loops, each with a similar code, but changing the conditional inside the for loop.

After some time thinking about possible solutions for this problem I came up with a not so obvious and interesting solution using some logic based on the observations of the examples.

The main idea

Instead of looking at the beginning of the string, how about looking at the end of it. The possible solutions are much simpler:

1. If the last character is Uppercase, then the whole String must be Uppercase.

2. If the last character is Lowercase, then the the whole string(skipping the first index) must be Lowercase.

We can skip the first character, now it doesn't matter at all!(well, for the most part). Because the last character actually tells us more about the string than the first character. As I mentioned before, the first character may be Uppercase or Lowercase, but the rest MUST be the same. So we just check for the case for the last character and then check for the same case for the rest of the string starting at index 1.

However we must consider one edge case, what if we have this string:

"aBCDEF"

The last character is Uppercase, and the rest of the string starting at index 1 is also Uppercase. That would be true according the previous logic. However, the result should be false, as the first character is not Uppercase. We can simply check for this edge case and that's it.

Explanation and Code

First, we check for the case of the last character. Let's say it is Uppercase:

"ABCEDFG" -> Last character "G" is Uppercase.

Then we check that all the other characters in the string starting at index 1 must be Uppercase.

The same with Lowercase. For example:

"abcdefg" -> Last character "g" is Lowercase

The logic for both cases is the same:

• if Uppercase, then all characters starting at index 1 must be Uppercase.
• if Lowercase, then all characters starting at index 1 must be Lowercase.

Because we have a binary decision here, we can use some propositional logic :)

Both sides of the conditional expression must be the same, otherwise we return false. That is exactly what the Exclusive or truth table provides.

So basically we can use the xor operator in Java "^" as the condition operator inside the for loop.

Finally, even before all of this we must check for the edge case. So if the last character is Lowercase and the first character is Uppercase, just return false.

The code is the following:

   public boolean detectCapitalUse(String word) {
        boolean hasToBeUppercase = Character.isUpperCase(word.charAt(word.length() - 1));
        if(hasToBeUppercase && Character.isLowerCase(word.charAt(0))) return false;
        for (int i = 1; i < word.length(); i++) {
           if(hasToBeUppercase ^ Character.isUpperCase(word.charAt(i))) return false;
        }
        return true;
    }

Always give proper names to your variables, that can make a big impact in the readability of your code.

The code is quite simple, and we just need to loop once through the characters in the string. As soon as the "xor" boolean expression is true for any string in the string, we return false. Otherwise the whole string complies with the constraints and we return true.

Complexity

• Time: O(n), we only loop once through the string.
• Space: O(1), we are only creating a boolean variable, which is independent of the size of the input.

Final comments:

Sometimes the solution can be more simple if we look at the problems from a different perspective. It is often the case in coding problems that it is easier to start from the "end" of the data structure (arrays, strings, lists). This was one of those cases.

Pay close attention to the examples and constraints of the problem. If possible, think of your own examples, and then given the information, try to observe some common patterns or properties that can give you more information about the problem.

Always try to think about different approaches. Try to generalize your solution so you don't repeat your code. For instance, I don't like the solution of Leetcode (approach 1), as it uses an if-else statement, both doing practically the same, except for the condition inside the for loop, which can be generalized as I demonstrated here.