3 Letters

AtCoder

IDagc052_e

Time2000ms

Memory256MB

Difficulty—

A string, consisting of letters `A`, `B`, and `C`, is called **good**, if every two consecutive letters are different. For example, strings `ABABAB` and `ABC` are good, while `ABBA` and `AABBCC` aren't. You are given two **good** strings $S$ and $T$ of length $N$. In one operation, you can choose any letter of $S$, and change it to another letter among `A`, `B`, and `C`, so that $S$ remains **good**. What's the smallest number of operations needed to transform $S$ into $T$? We can prove that it can always be done in a finite number of operations. ## Constraints * $1\le N \le 5\cdot 10^5$ * $S$ is a **good** string of length $N$ consisting of `A`, `B`, and `C` * $T$ is a **good** string of length $N$ consisting of `A`, `B`, and `C` ## Input Input is given from Standard Input in the following format: $N$ $S$ $T$ [samples]

Samples

Input #1

4
CABC
CBAC

Output #1

6

Here is one possible sequence of operations of length $6$:
`CABC` $\to$ `BABC` $\to$ `BCBC` $\to$ `BCAC` $\to$ `ACAC` $\to$ `ABAC` $\to$ `CBAC`
It can be shown that $6$ operations are necessary for this case.

Input #2

10
ABABABABAB
BABABABABA

Output #2

API Response (JSON)

{
  "problem": {
    "name": "3 Letters",
    "description": {
      "content": "A string, consisting of letters `A`, `B`, and `C`, is called **good**, if every two consecutive letters are different. For example, strings `ABABAB` and `ABC` are good, while `ABBA` and `AABBCC` aren'",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc052_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A string, consisting of letters `A`, `B`, and `C`, is called **good**, if every two consecutive letters are different. For example, strings `ABABAB` and `ABC` are good, while `ABBA` and `AABBCC` aren'...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments