Today’s daily problem is an extension of yesterday’s. Go ahead and read that one for the basics, as I won’t repeat them again, and will instead focus on the differences.

We’re once again given a string that Alice typed, however this time we’re told that Alice may have made multiple mistakes. Honestly this seems like Alice’s problem not our’s, but here we are. We’re also give the minimum length of the string that she meant to type. We’re asked to return the number of possible strings that Alice meant to type based on what she did type and the minimum length, modulo 10^9 - 7 because the number could be huge (that’s not really an issue with Python, though operating on really large numbers can get quite slow).

The first example is aabbccdd with a minimum length of 7. We’re told the result is 5, and these are the strings:

  1. aabbccdd
  2. aabbccd
  3. aabbcdd
  4. aabccdd
  5. abbccdd

Of course, this makes perfect sense. Given that that provided string is only eight characters long, and the string Alice had meant to type was at least seven characters long (and the first character of every repeated set must have been intentional), the only options are:

  1. All of them are intentional.
  2. One character in one group was unintentional.

Otherwise, if more than one character was unintentional, she couldn’t have typed a seven-or-more character string.

Armed with this information, it’s pretty easy to figure out how many possible strings Alice could have meant to type, based on the input. Since the first letter of a group has to be intentional, then a second letter provides two options, a third three, a fourth four, and so on. For the example aabbccdd, the total number of original strings (disregarding the minimum length) is 16–two options per group times four groups.

Since we know the upper bound, the trick is figuring out how many possible strings fall below the provided minimum length. Given that if we know the number of combinations for some prefix of the given string we can figure out the number of combinations given the next character in the string, this is a perfect job for dynamic programming (which shows up on Leetcode far more than it shows up in real interviews, in my experience).

I think it will be easier to paste in the code and explain via comments.

class Solution:
    MOD = 10**9 + 7

    def possibleStringCount(self, word: str, k: int) -> int:
        if len(word) < k:
            return 0

        groups = [1]
        for i in range(1, len(word)):
            if word[i] == word[i-1]:
                groups[-1] += 1
            else:
                groups.append(1)

        ngroups = len(groups)
        
        total = 1
        for g in groups:
            total = (total * g) % self.MOD

        # Since each group will add at least one to the length of the
        # string, if k is less than or equal to the number of groups
        # then all possible strings are valid.
        if k <= ngroups:
            return total

        # We only care about the extra characters that don't come from
        # the fixed one-per-group characters.
        extra = k - len(groups)
        dp = [0] * extra
        dp[0] = 1 # one way to type zero characters

        for g in groups:
            # Ignoring the first character that we've already accounted for
            max_add = g - 1
            new_dp = [0] * extra
            s = 0
            for i in range(extra):
                s += dp[i]
                # We can't take everything before into account because some
                # prefixes can't possibly have reached the current prefix.
                if i > max_add:
                    s -= dp[i - max_add - 1]
                new_dp[i] = s % self.MOD
            dp = new_dp
        
        invalid = sum(dp) % self.MOD
        return (total - invalid) % self.MOD

Not gonna lie, this took me a long time to figure out. I don’t know that I’ve ever done dynamic programming IRL, and though it comes up on Leetcode quite a lot, many companies have a policy to avoid DP questions during interviews because they tend to boil down to the candidate realizing the “one weird trick” that solves the problem, which limits the signal you can get from an interview where the candidate misses that trick.