Score : $575$ points

问题描述

你给定一个字符串 $S$。通过在字符串 $S$ 上执行零次或多次以下操作，找到可以得到的最短字符串长度。

• 在字符串中选择一个连续出现的 of 子串以及一个整数 $i$，使得 $0 \leq i \leq K$。然后，从字符串中移除这个 of 及其后面紧随的 $i$ 个字符。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a string $S$. Find the minimum length of a string that can be obtained by performing the following operation on the string $S$ zero or more times.

• Choose a contiguous occurrence of of in the string and an integer $i$ between $0$ and $K$, inclusive. Then, remove the of and the following $i$ characters from the string.

Constraints

• $0 \leq K < |S| \leq 300$
• $K$ is an integer.
• $S$ is a string consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

$S$

$K$

Output

Print the answer.

Sample Input 1

keyofscience
3

Sample Output 1

7

By choosing the of formed by the fourth and fifth characters and setting $i = 3$, you can remove ofsci from keyofscience and get keyence.
It is impossible to reduce the length of the string to $6$ or less by repeating the operation, so the answer is $7$.

Sample Input 2

oofsifffence
3

Sample Output 2

2

Sample Input 3

ooofff
5

Sample Output 3

0

Sample Input 4

okeyencef
4

Sample Output 4

9

update @ 2024/3/10 01:48:46