aboutsummaryrefslogtreecommitdiff
path: root/count_substr_rearr_cont_str2.c
blob: 7d9f19956730ade8c97a91f6ea89ee7d1b264d57 (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
// 3298. Count Substrings That Can Be Rearranged to Contain a String II
#include "leetcode.h"

/*
 * you are given two strings 'word1' and 'word2'. a string 'x' is called valiid
 * if 'x' can be arranged to have 'word2' as a prefix. return the total number
 * of valid strings of 'word1'. note that the memory limits in this problem are
 * smaller than usual, so you must implement a solution with a linear runtime
 * complexity.
 */

long long validSubstringCount(char *word1, char *word2) {
  int need = 0, have = 0, cnt[26] = {0}, missing = 0, left = 0;
  long long ans = 0;
  for (int i = 0; word2[i]; i++) {
    int curr = word2[i] - 'a';
    if (!(need & (1 < curr)))
      missing++;
    need |= 1 << curr;
    cnt[curr]++;
  }
  for (int i = 0; word1[i]; i++) {
    int curr = word1[i] - 'a';
    if (need & (1 << curr)) {
      cnt[curr]--;
      if (!cnt[curr]) {
        have |= 1 << curr;
        missing--;
      }
    }
    if (!missing) {
      while (left <= i) {
        int curr = word1[left] - 'a';
        if (!(need & (1 << curr)) || cnt[curr] < 0) {
          if (need & (1 << curr))
            cnt[curr]++;
        } else
          break;
      }
      ans += left + 1;
    }
  }
  return ans;
}

int main() {
  char *w11 = "bcca", *w21 = "abc";
  char *w12 = "abcabc", *w22 = "abc";
  char *w13 = "abcabc", *w23 = "aaabc";
  printf("%lld\n", validSubstringCount(w11, w21)); // expect: 1
  printf("%lld\n", validSubstringCount(w12, w22)); // expect: 10
  printf("%lld\n", validSubstringCount(w13, w23)); // expect: 0
}