C. Plasticine zebra

Codeforces

IDCF1025C

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsimplementation

English · Original

Chinese · Translation

Formal · Original

Is there anything better than going to the zoo after a tiresome week at work? No wonder Grisha feels the same while spending the entire weekend accompanied by pretty striped zebras. Inspired by this adventure and an accidentally found plasticine pack (represented as a sequence of black and white stripes), Grisha now wants to select several consequent (contiguous) pieces of alternating colors to create a zebra. Let's call the number of selected pieces the length of the zebra. Before assembling the zebra Grisha can make the following operation $0$ or more times. He splits the sequence in some place into two parts, then reverses each of them and sticks them together again. For example, if Grisha has pieces in the order "_bwbbw_" (here '_b_' denotes a black strip, and '_w_' denotes a white strip), then he can split the sequence as _bw|bbw_ (here the vertical bar represents the cut), reverse both parts and obtain "_wbwbb_". Determine the maximum possible length of the zebra that Grisha can produce. ## Input The only line contains a string $s$ ($1 \le |s| \le 10^5$, where $|s|$ denotes the length of the string $s$) comprised of lowercase English letters '_b_' and '_w_' only, where '_w_' denotes a white piece and '_b_' denotes a black piece. ## Output Print a single integer — the maximum possible zebra length. [samples] ## Note In the first example one of the possible sequence of operations is _bwwwbww|bw_ $\to$ _w|wbwwwbwb_ $\to$ _**wbwbw**wwbw_, that gives the answer equal to $5$. In the second example no operation can increase the answer.

在辛苦工作了一周之后，还有什么比去动物园更美好的呢？难怪格里沙在整个周末与漂亮的条纹斑马相伴时也感到如此愉悦。受这次冒险的启发，以及偶然找到的一包橡皮泥（表示为一系列黑白条纹），格里沙现在希望选择若干连续的、颜色交替的片段来制作一条斑马。我们称所选片段的数量为斑马的长度。在组装斑马之前，格里沙可以执行以下操作零次或多次：他将序列在某个位置切成两部分，然后分别反转这两部分，再将它们重新拼接在一起。例如，如果格里沙的片段顺序为 "_bwbbw_"（其中 '_b_' 表示黑色条纹，'_w_' 表示白色条纹），他可以将序列切为 _bw|bbw_（竖线表示切口），反转两部分后得到 "_wbwbb_"。请确定格里沙能制作出的斑马的最大可能长度。输入仅有一行，包含一个字符串 $s$（$1 lt.eq | s | lt.eq 10^5$，其中 $| s |$ 表示字符串 $s$ 的长度），字符串仅由小写英文字母 '_b_' 和 '_w_' 组成，其中 '_w_' 表示白色片段，'_b_' 表示黑色片段。请输出一个整数 —— 格里沙能制作出的斑马的最大可能长度。在第一个示例中，一种可能的操作序列是 _bwwwbww|bw_ $arrow.r$ _w|wbwwwbwb_ $arrow.r$ _*wbwbw*wwbw_，得到的答案为 $5$。在第二个示例中，任何操作都无法增加答案。 ## Input The only line contains a string $s$ ($1 lt.eq | s | lt.eq 10^5$, where $| s |$ denotes the length of the string $s$) comprised of lowercase English letters '_b_' and '_w_' only, where '_w_' denotes a white piece and '_b_' denotes a black piece. ## Output Print a single integer — the maximum possible zebra length. [samples] ## Note In the first example one of the possible sequence of operations is _bwwwbww|bw_ $arrow.r$ _w|wbwwwbwb_ $arrow.r$ _*wbwbw*wwbw_, that gives the answer equal to $5$.In the second example no operation can increase the answer.

**Definitions** Let $ s \in \{b, w\}^n $ be a string of length $ n $, where $ n \in \mathbb{Z} $, $ 1 \leq n \leq 10^5 $. A *zebra* is a contiguous substring of $ s $ in which no two adjacent characters are equal (i.e., an alternating sequence of 'b' and 'w'). An *operation* consists of: - Choosing an index $ k \in \{0, 1, \dots, n\} $ (split point), - Splitting $ s $ into two parts: $ s_1 = s[0:k] $, $ s_2 = s[k:n] $, - Reversing each part: $ s_1' = \text{reverse}(s_1) $, $ s_2' = \text{reverse}(s_2) $, - Concatenating: $ s' = s_1' + s_2' $. Let $ \mathcal{O}(s) $ denote the set of all strings obtainable from $ s $ via zero or more operations. **Constraints** 1. $ s $ contains only characters 'b' and 'w'. 2. Operations may be applied any number of times (including zero). **Objective** Compute: $$ \max_{s' \in \mathcal{O}(s)} \left( \max_{\substack{1 \leq i \leq j \leq n \\ s'[i:j] \text{ is alternating}}} (j - i + 1) \right) $$ That is, the maximum length of a contiguous alternating substring achievable in any string obtainable from $ s $ via the allowed operations.

Samples

Input #1

bwwwbwwbw

Output #1

Input #2

bwwbwwb

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Plasticine zebra",
    "description": {
      "content": "Is there anything better than going to the zoo after a tiresome week at work? No wonder Grisha feels the same while spending the entire weekend accompanied by pretty striped zebras. Inspired by this ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1025C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Is there anything better than going to the zoo after a tiresome week at work? No wonder Grisha feels the same while spending the entire weekend accompanied by pretty striped zebras.\n\nInspired by this ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在辛苦工作了一周之后，还有什么比去动物园更美好的呢？难怪格里沙在整个周末与漂亮的条纹斑马相伴时也感到如此愉悦。\n\n受这次冒险的启发，以及偶然找到的一包橡皮泥（表示为一系列黑白条纹），格里沙现在希望选择若干连续的、颜色交替的片段来制作一条斑马。我们称所选片段的数量为斑马的长度。\n\n在组装斑马之前，格里沙可以执行以下操作零次或多次：他将序列在某个位置切成两部分，然后分别反转这两部分，再将它们重新拼接在...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{b, w\\}^n $ be a string of length $ n $, where $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10^5 $.\n\nA *zebra* is a contiguous substring of $ s $ in which no two adjacent chara...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments