M. Decomposition into Good Strings

Codeforces

IDCF10097M

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Sometimes, in string problems you have to find a string satisfying some conditions. The authors again were too lazy to think of a tricky term for such string, so they called it _good_. A string is called good if it contains exactly k different characters. You are given a string s. Find the minimal number of good strings so that their concatenation is s. The first line contains an integer k (1 ≤ k ≤ 26). The second line contains a string s (1 ≤ |s| ≤ 200000), consisting of lowercase Latin letters. For every prefix of s, starting from the prefix consisting of the first character of s, and ending with s itself, output the minimal number of good strings so that their concatenation is this prefix. Solutions will be tested more carefully this way, won't they? If for some prefix the decomposition into good strings isn't possible, output «_-1_» for it. ## Input The first line contains an integer k (1 ≤ k ≤ 26).The second line contains a string s (1 ≤ |s| ≤ 200000), consisting of lowercase Latin letters. ## Output For every prefix of s, starting from the prefix consisting of the first character of s, and ending with s itself, output the minimal number of good strings so that their concatenation is this prefix. Solutions will be tested more carefully this way, won't they?If for some prefix the decomposition into good strings isn't possible, output «_-1_» for it. [samples]

**Definitions** Let $ k \in \mathbb{Z} $ with $ 1 \leq k \leq 26 $. Let $ s = s_1 s_2 \dots s_n $ be a string of length $ n = |s| $, where $ s_i \in \{a, b, \dots, z\} $. A string is *good* if it contains exactly $ k $ distinct characters. **Constraints** $ 1 \leq n \leq 200000 $ **Objective** For each prefix $ s[1..i] $ (for $ i = 1 $ to $ n $), compute the minimal number $ m_i $ of good strings whose concatenation equals $ s[1..i] $. If no such decomposition exists, set $ m_i = -1 $. Output $ m_1, m_2, \dots, m_n $.

API Response (JSON)

{
  "problem": {
    "name": "M. Decomposition into Good Strings",
    "description": {
      "content": "Sometimes, in string problems you have to find a string satisfying some conditions. The authors again were too lazy to think of a tricky term for such string, so they called it _good_. A string is ca",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sometimes, in string problems you have to find a string satisfying some conditions. The authors again were too lazy to think of a tricky term for such string, so they called it _good_.\n\nA string is ca...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq 26 $.  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n = |s| $, where $ s_i \\in \\{a, b, \\dots, z\\} $.  \nA string is *good* if i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments