Reversed LCS

AtCoder

IDagc021_d

Time2000ms

Memory256MB

Difficulty—

Takahashi has decided to give a string to his mother. The _value_ of a string $T$ is the length of the longest common subsequence of $T$ and $T'$, where $T'$ is the string obtained by reversing $T$. That is, the value is the longest length of the following two strings that are equal: a subsequence of $T$ (possibly non-contiguous), and a subsequence of $T'$ (possibly non-contiguous). Takahashi has a string $S$. He wants to give her mother a string of the highest possible value, so he would like to change at most $K$ characters in $S$ to any other characters in order to obtain a string of the highest possible value. Find the highest possible value achievable. ## Constraints * $1 \leq |S| \leq 300$ * $0 \leq K \leq |S|$ * $S$ consists of lowercase English letters. * $K$ is an integer. ## Input Input is given from Standard Input in the following format: $S$ $K$ [samples]

Samples

Input #1

abcabcabc
1

Output #1

7

Changing the first character to `c` results in `cbcabcabc`. Let this tring be $T$, then one longest common subsequence of $T$ and $T'$ is `cbabcbc`, whose length is $7$.

Input #2

atcodergrandcontest
3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Reversed LCS",
    "description": {
      "content": "Takahashi has decided to give a string to his mother. The _value_ of a string $T$ is the length of the longest common subsequence of $T$ and $T'$, where $T'$ is the string obtained by reversing $T$. T",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc021_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi has decided to give a string to his mother.\nThe _value_ of a string $T$ is the length of the longest common subsequence of $T$ and $T'$, where $T'$ is the string obtained by reversing $T$. T...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments