Find the Original Typed String II

For this question, first if we denote word to have n distinct sections of letters (e.g. aabbbbccdd has 4 distinct sections of letters), then we know that at a bare minimum, the possible original string must be at least of length n.

First off for this question, realise to calculate the total possible original strings, it just requires us to multiply together the frequencies of each segment.

Thus, it makes sense to pre-calculate the frequency of each segment and store it into a freq array (to use later). For example, the freq array for string aabbbbccdd would be [2, 4, 2, 2].

Then, given this freq array, it allows us to formulate a dp algorithm. To define the recurrence relationship, let us iterate through freq using index i, where 0 <= i < freq.size(), and define dp_(i)[j] as the number of words that can be formed of length j using only the first i sections of letters, where 0 <= j < k.

Now, if we iterate to index i+1 in the recurrence relation, we are adding freq[i+1] of the letter, let us call it a, into the pool. This means to calculate dp_(i+1)[j], its the same as summing up dp_(i)[j-1], dp_(i)[j-2], ... and dp_(i)[j-freq[i+1]] (let us assume for simplicity that j > freq[i+1]). This is because we can simply:

add one a to every unique word of length j-1 in dp(i)[j-1] to get a unique word of length j
add two a to every unique word of length j-2 in dp(i)[j-2] to get a unique word of length j
...
add freq[i+1] a to every unique word of length j-freq[i+1] in dp(i)[j-freq[i+1]] to get a unique word of length j

For example, using this algorithm on aabbbbccdd, for k = 6, on each iteration. Initially our array should look like:

dp(-1) = [1, 0, 0, 0, 0, 0]

since we not "added" any letters into the pool (adding -1 for clarity).

dp_(0) = [0, 1, 1, 0, 0, 0]

as a simple example, since freq[0] = 2, we know that:

dp_(0)[1] = dp(-1)[0] = 1 as we are adding 1 a to an empty string

dp_(0)[2] = dp(-1)[1] + dp(-1)[0] = 1 as we are adding 2 a to an empty string

dp_(1) = [0, 0, 1, 2, 2, 2]

slightly more complicated; we will run through dp_(1)[5] as an example:

dp_(1)[5] = dp(0)[4] + dp(0)[3] + dp(0)[2] + dp(0)[1] as we can effectively add 1, 2, 3 or 4 bs to their respective strings to get original strings of length 5

dp_(2) = [0, 0, 0, 1, 3, 4]

you can contrast the previous working with dp_(2)[4]:

dp_(2)[4] = dp(1)[3] + dp(1)[2] as we can effectively add 1 or 2 cs to their respective strings to get an original strings of length 5

dp_(3) = [0, 0, 0, 0, 1, 4]

After iterating through the entirety of k, we can simply just delete from the number of total possible original strings, (which we can just calculate by multiplying together the frequencies of each segment) the number of possible strings that are smaller than k, which should just be the sum of all the elements of dp (since it is of length k, it contains the count of possible strings of length 0 to length k-1).

code

class Solution {
private:
    long long MOD = 1e9+7;
public:
    int possibleStringCount(string word, int k) {
        vector<int> freq;
            int currFreq = 1;
        for (int i = 1; i < word.size(); ++i) {
            if (word[i] == word[i-1]) {
                ++currFreq;
            } else {
                freq.push_back(currFreq);
                currFreq = 1;
            }
        }
        freq.push_back(currFreq);

        long long ans = 1;
        for (int i = 0; i < freq.size(); ++i) {
            ans = (ans * freq[i]) % MOD;
        }

        if (freq.size() > k) {
            return ans;
        }

        vector<int> dp(k, 0);
        dp[0] = 1;

        for (int i = 0; i < freq.size(); ++i) {
            vector<int> newDp(k);
            long long counter = 0;
            for (int j = 0; j < k; ++j) {
                if (j > 0) {
                    counter = (counter + dp[j-1]) % MOD;
                }
                if (j > freq[i]) {
                    counter = (counter - dp[j-freq[i]-1] + MOD) % MOD;
                }
                newDp[j] = counter;
            }
            dp = newDp;
        }

        for (int i = freq.size(); i < k; ++i) {
            ans = (ans - dp[i] + MOD) % MOD;
        }
        return ans;
    }
};

complexity

Time: O(n + k^2) where n is the number of characters inside word and k is literally the input k

Space: O(n + k)

time taken

30 minutes and 3 seconds