E. Maximum Questions

Codeforces

IDCF900E

Time2000ms

Memory256MB

Difficulty—

data structuresdpstrings

English · Original

Chinese · Translation

Formal · Original

Vasya wrote down two strings _s_ of length _n_ and _t_ of length _m_ consisting of small English letters '_a_' and '_b_'. What is more, he knows that string _t_ has a form "_abab..._", namely there are letters '_a_' on odd positions and letters '_b_' on even positions. Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string _s_ were replaced by character '_?_'. Let's call a sequence of positions _i_, _i_ + 1, ..., _i_ + _m_ - 1 as _occurrence_ of string _t_ in _s_, if 1 ≤ _i_ ≤ _n_ - _m_ + 1 and _t_1 = _s__i_, _t_2 = _s__i_ + 1, ..., _t__m_ = _s__i_ + _m_ - 1. The boy defines the _beauty_ of the string _s_ as maximum number of disjoint occurrences of string _t_ in _s_. Vasya can replace some letters '_?_' with '_a_' or '_b_' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string _s_ is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the length of _s_. The second line contains the string _s_ of length _n_. It contains small English letters '_a_', '_b_' and characters '_?_' only. The third line contains a single integer _m_ (1 ≤ _m_ ≤ 105) — the length of _t_. The string _t_ contains letters '_a_' on odd positions and '_b_' on even positions. ## Output Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string _s_ the maximum possible. [samples] ## Note In the first sample string _t_ has a form '_a_'. The only optimal option is to replace all characters '_?_' by '_a_'. In the second sample using two replacements we can make string equal to "_**aba**?**aba**??_". It is impossible to get more than two occurrences.

Vasya 写下了两个字符串 #cf_span[s]（长度为 #cf_span[n]）和 #cf_span[t]（长度为 #cf_span[m]），均由小写英文字母 '_a_' 和 '_b_' 组成。此外，他知道字符串 #cf_span[t] 的形式为 "_abab..._"，即奇数位置为字母 '_a_'，偶数位置为字母 '_b_'。一天早晨，Vasya 发现他的字符串被破坏了：字符串 #cf_span[s] 中的一些字母被替换成了字符 '_?_'。我们称位置序列 #cf_span[i, i + 1, ..., i + m - 1] 为字符串 #cf_span[t] 在 #cf_span[s] 中的一个 _出现_，当且仅当 #cf_span[1 ≤ i ≤ n - m + 1] 且 #cf_span[t1 = si, t2 = si + 1, ..., tm = si + m - 1]。男孩定义字符串 #cf_span[s] 的 _美丽值_ 为 #cf_span[s] 中互不重叠的 #cf_span[t] 出现的最大数量。Vasya 可以将某些 '_?_' 替换为 '_a_' 或 '_b_'（不同位置可以替换为不同字母）。Vasya 希望进行一些替换，使得字符串 #cf_span[s] 的美丽值尽可能大。在所有能使美丽值最大的方案中，他希望选择替换次数最少的那个。请找出他需要进行的最少替换次数。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）— 字符串 #cf_span[s] 的长度。第二行包含长度为 #cf_span[n] 的字符串 #cf_span[s]，仅包含小写英文字母 '_a_'、'_b_' 和字符 '_?_'。第三行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 105]）— 字符串 #cf_span[t] 的长度。字符串 #cf_span[t] 在奇数位置为 '_a_'，在偶数位置为 '_b_'。请输出一个整数 —— Vasya 为使字符串 #cf_span[s] 的美丽值达到最大可能值所需进行的最少替换次数。在第一个样例中，字符串 #cf_span[t] 的形式为 '_a_'。唯一最优的选择是将所有 '_?_' 替换为 '_a_'。在第二个样例中，通过两次替换，我们可以使字符串变为 "_*aba*?*aba*??_"。不可能获得超过两个出现。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）— 字符串 #cf_span[s] 的长度。第二行包含长度为 #cf_span[n] 的字符串 #cf_span[s]，仅包含小写英文字母 '_a_'、'_b_' 和字符 '_?_'。第三行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 105]）— 字符串 #cf_span[t] 的长度。字符串 #cf_span[t] 在奇数位置为 '_a_'，在偶数位置为 '_b_'。 ## Output 请输出一个整数 —— Vasya 为使字符串 #cf_span[s] 的美丽值达到最大可能值所需进行的最少替换次数。 [samples] ## Note 在第一个样例中，字符串 #cf_span[t] 的形式为 '_a_'。唯一最优的选择是将所有 '_?_' 替换为 '_a_'。在第二个样例中，通过两次替换，我们可以使字符串变为 "_*aba*?*aba*??_"。不可能获得超过两个出现。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq m \leq n \leq 10^5 $. Let $ s \in \{a, b, ?\}^n $ be the corrupted string. Let $ t \in \{a, b\}^m $ be the target string defined by: $$ t_i = \begin{cases} a & \text{if } i \text{ is odd}, \\ b & \text{if } i \text{ is even}. \end{cases} $$ An *occurrence* at position $ i $ (for $ 1 \leq i \leq n - m + 1 $) is a substring $ s[i:i+m-1] $ such that $ s[i+j-1] = t_j $ for all $ j \in \{1, \dots, m\} $, after replacing all $ ? $ in $ s $ with $ a $ or $ b $. Two occurrences are *disjoint* if their intervals $[i, i+m-1]$ and $[i', i'+m-1]$ do not overlap. The *beauty* of $ s $ is the maximum number of disjoint occurrences of $ t $ that can be formed by replacing $ ? $ with $ a $ or $ b $. **Constraints** 1. $ s $ contains only characters from $ \{a, b, ?\} $. 2. $ t $ is fixed as alternating $ a, b, a, b, \dots $ of length $ m $. 3. Replacements may only change $ ? $ to $ a $ or $ b $. **Objective** Find the *minimum number of replacements* (i.e., number of $ ? $ changed) required to achieve the *maximum possible beauty* (i.e., maximum number of disjoint occurrences of $ t $).

Samples

Input #1

5
bb?a?
1

Output #1

Input #2

9
ab??ab???
3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Maximum Questions",
    "description": {
      "content": "Vasya wrote down two strings _s_ of length _n_ and _t_ of length _m_ consisting of small English letters '_a_' and '_b_'. What is more, he knows that string _t_ has a form \"_abab..._\", namely there ar",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF900E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasya wrote down two strings _s_ of length _n_ and _t_ of length _m_ consisting of small English letters '_a_' and '_b_'. What is more, he knows that string _t_ has a form \"_abab..._\", namely there ar...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasya 写下了两个字符串 #cf_span[s]（长度为 #cf_span[n]）和 #cf_span[t]（长度为 #cf_span[m]），均由小写英文字母 '_a_' 和 '_b_' 组成。此外，他知道字符串 #cf_span[t] 的形式为 \"_abab..._\"，即奇数位置为字母 '_a_'，偶数位置为字母 '_b_'。\n\n一天早晨，Vasya 发现他的字符串被破坏了：字符串 #cf...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq m \\leq n \\leq 10^5 $.  \nLet $ s \\in \\{a, b, ?\\}^n $ be the corrupted string.  \nLet $ t \\in \\{a, b\\}^m $ be the target string defined by:  ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments