Today’s daily problem is an easy one.

You’re given a string that contains only lowercase letters. The example given are:

abbcccc
abcd
aaaa

The setup for the problem is that Alice is typing, but she’s clumsy and may press a key twice while typing a string, but will only do it at most once. Given the string that Alice typed, return the total number of possible strings she could have been intending to type.

Let’s take a look at the first example:

Input: word = "abbcccc"

Output: 5

Explanation:

The possible strings are: "abbcccc", "abbccc", "abbcc", "abbc", and "abcccc".

So while Alice is typing:

  1. a : it’s the first letter, it can’t possibly have been a duplicate.
  2. b : it’s different than the letter before it, so it can’t possibly be a duplicate either.
  3. b : it’s the same as the previous letter, so it could either be a duplicate or intentional.
  4. c : it’s different than the letter before it, so it can’t be a duplicate.
  5. c : it’s the same as the previous letter, so it could either be a duplicate or intentional.
  6. c : it’s the same as the previous letter, so it could either be a duplicate or intentional.
  7. c : it’s the same as the previous letter, so it could either be a duplicate or intentional.
  8. c : it’s the same as the previous letter, so it could either be a duplicate or intentional.

After 1 and 2, there’s still only one possible string it could be: ab. But after 3, there are two possible strings–either ab (the second b was a mistake) or abb (the second b was intentional). After 4, there are still two strings, abc and abbc, as the first c can only be intentional.

Then for each of the following cs, each creates a new possible word, because remember Alice only messes up at most once per string. So from abc and abbc we get abcc (the second c was intentional), abbcc (both the second b earlier and the second c were intentional), and abcc (we already “used” our mistake with the second b, so the second c must be intentional).

And so on.

Because there can be at most one mistake in the string, the answer doesn’t grow geometrically, as each additional potential mistake only adds a single string to the collection–the version that contains no mistakes splits into a version that still contains no mistakes, and one that had its mistake on the current letter.

This means that what we really need to do is count how many letters are duplicates of the letter before them, and add one (for the initial invariant string always created by the first letter).

class Solution:
    def possibleStringCount(self, word: str) -> int:
        return 1 + sum(
            word[i-1] == word[i]
            for i 
            in range(1, len(word))
        )

Remember that in Python as in C/C++, boolean values act like 1 and 0 when used in math.