Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 2

Description

Find the Original Typed String II

Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.

You are given a string word, which represents the final output displayed on Alice's screen. You are also given a positive integer k.

Return the total number of possible original strings that Alice might have intended to type, if she was trying to type a string of size at least k.

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= word.length <= 5 * 105
• word consists only of lowercase English letters.
• 1 <= k <= 2000

Solution

class Solution {
  const int MOD = 1e9 + 7;
public:
  int possibleStringCount(string word, int k) {
    int count = 0;
    long long total = 1;
    vector<int> counts;
    char prev = word.front();
    for(auto c : word) {
      if(c == prev) {
        count += 1;
        continue;
      }
      counts.push_back(count);
      total *= count;
      total %= MOD;
      count = 1;
      prev = c;
    }
    counts.push_back(count);
    total *= count;
    total %= MOD;
    
    vector<vector<int>> dp(2, vector<int>(k + 1, 0));
    for(int i = 1; i <= min(counts.front(), k - 1); ++i) dp[0][i] = 1;
    vector<int> prefix(k + 1, 0);
    int segs = counts.size();

    for(int i = 1; i < min(segs, k); ++i) {
      int parity = (i & 1);
      prefix[0] = dp[!parity][0];
      for(int j = 1; j <= k; ++j) {
        prefix[j] = (prefix[j - 1] + dp[!parity][j]) % MOD;
      }

      for(int j = 1; j <= k; ++j) {
        int pos = max(i, j - counts[i]);
        dp[parity][j] = (prefix[j - 1] - prefix[pos - 1] + MOD) % MOD;
      }
    }

    int notValid = 0;
    int parity = !(min(segs, k) & 1);
    for(int i = 0; i < k; ++i) {
      notValid += dp[parity][i];
      notValid %= MOD;
    }
    return (total - notValid + MOD) % MOD;
  }
};

// Accepted
// 846/846 cases passed (656 ms)
// Your runtime beats 10.46 % of cpp submissions
// Your memory usage beats 47.67 % of cpp submissions (80 MB)