J. Divide The String

Codeforces

IDCF10279J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You have a string $s$ consisting of lowercase letters of the Latin alphabet. You need to split this string into substrings according to the following requirements: Therefore, if we concatenate all the resulting substrings in the same order, we'll get the original string $s$. A substring of the string $s$ is a non-empty sequence of consecutive letters of the string $s$. For example, the string _aadddzxxz_ can be split into substrings _aa_, _ddd_ and _zxxz_. Find the maximum number of substrings that the string $s$ can be split into, and also the sizes of each of these substrings. If the string $s$ cannot be split as described, report it. The first line contains an integer $n$ ($2 <= n <= 4 dot.op 10^5$) — the length of the string $s$. The second line contains a string $s$ of length $n$ consisting of lowercase letters of the Latin alphabet. If the string cannot be split into substrings of greater than one length that start and end with the same letter, print $-1$. Otherwise, in the first line, print $k$ — the maximum number of substrings that the string $s$ can be split into. In the second line, print $k$ integers — the sizes of substrings that the string $s$ can be split into, in order from left to right. The sum of the output $k$ numbers must be equal to $n$. In the first example, the string can be split into two substrings of length two, each of which starts and ends with the letter _a_. In the second example, the string can be split into three substrings _abcbca_, _ccbbc_ and _abca_. ## Input The first line contains an integer $n$ ($2 <= n <= 4 dot.op 10^5$) — the length of the string $s$.The second line contains a string $s$ of length $n$ consisting of lowercase letters of the Latin alphabet. ## Output If the string cannot be split into substrings of greater than one length that start and end with the same letter, print $-1$.Otherwise, in the first line, print $k$ — the maximum number of substrings that the string $s$ can be split into. In the second line, print $k$ integers — the sizes of substrings that the string $s$ can be split into, in order from left to right. The sum of the output $k$ numbers must be equal to $n$. [samples] ## Note In the first example, the string can be split into two substrings of length two, each of which starts and ends with the letter _a_.In the second example, the string can be split into three substrings _abcbca_, _ccbbc_ and _abca_.

**Definitions** Let $ s \in \Sigma^n $ be a string of length $ n $, where $ \Sigma = \{a, b, \dots, z\} $. A valid substring is a contiguous non-empty substring $ s[i:j] $ (1-indexed) such that $ s[i] = s[j] $ and $ j - i + 1 \geq 2 $. **Constraints** 1. $ 2 \leq n \leq 4 \cdot 10^5 $ 2. Each substring in the partition must satisfy: - Length $ \geq 2 $ - First and last characters are equal 3. The substrings must be contiguous and non-overlapping, covering the entire string $ s $. **Objective** Find the maximum number $ k $ of such valid substrings and their lengths $ \ell_1, \ell_2, \dots, \ell_k $ such that: - $ \sum_{i=1}^k \ell_i = n $ - For each $ i $, $ \ell_i \geq 2 $ and $ s[\text{start}_i] = s[\text{end}_i] $ If no such partition exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "J. Divide The String",
    "description": {
      "content": "You have a string $s$ consisting of lowercase letters of the Latin alphabet. You need to split this string into substrings according to the following requirements: Therefore, if we concatenate all t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10279J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a string $s$ consisting of lowercase letters of the Latin alphabet.\n\nYou need to split this string into substrings according to the following requirements:\n\nTherefore, if we concatenate all t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^n $ be a string of length $ n $, where $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nA valid substring is a contiguous non-empty substring $ s[i:j] $ (1-indexed) such that $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments