aboutsummaryrefslogtreecommitdiff
path: root/find_original_typed_str2.c
blob: 9d565f8aeba5760ee2bf93884db5a5de71137a3a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 3333. Find the Original Typed String II
#include "leetcode.h"

/*
 * 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 modul 10^9+7.
 */

int possibleStringCount(char *word, int k) {
  long long prod = 1, mod = 1e9 + 7;
  int g[2000], m = 0, n = strlen(word);
  for (int i = 1, cnt = 1; i <= n; ++i) {
    if (i < n && word[i] == word[i - 1])
      ++cnt;
    else {
      g[m++] = cnt - 1;
      prod = (prod * cnt) % mod;
      cnt = 1;
    }
  }
  if (k <= m)
    return (int)prod;
  int dp[2][2001] = {{1}}, ps[2001] = {0}, sz = m;
  for (int i = 0; i < sz; ++i) {
    ps[0] = 0;
    for (int j = 0; j < k - sz; ++j)
      ps[j + 1] = (ps[j] + dp[i % 2][j]) % mod;
    for (int j = 0; j < k - sz; ++j) {
      int low = j - g[i];
      if (low < 0)
        low = 0;
      dp[!(i % 2)][j] = (ps[j + 1] - ps[low]) % mod;
      if (dp[!(i % 2)][j] < 0)
        dp[!(i % 2)][j] += mod;
    }
  }
  long long ans = 0;
  for (int i = 0; i < k; ++i)
    ans = (ans + dp[sz % 2][i]) % mod;
  return (int)((mod + prod - ans) % mod);
}

int main() {
  char *w1 = "aabbccdd", *w2 = "aabbccdd", *w3 = "aaabbb";
  printf("%d\n", possibleStringCount(w1, 7)); // expect: 5
  printf("%d\n", possibleStringCount(w2, 8)); // expect: 1
  printf("%d\n", possibleStringCount(w3, 3)); // expect: 8
}