M. Two Operations

Codeforces

IDCF10226M

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Ayoub has a string $S$ consists of only lower case Latin letters, and he wants you to make some operations on it: Ayoub wants you to make the string lexicographically maximal using the mentioned operations as many times as you want, can you help him? String $x = x_1 x_2... x_{| x |}$ is lexicographically larger than string $y = y_1 y_2... y_{| y |}$, if either $| x | > | y |$ and $x_1 = y_1, x_2 = y_2,..., x_{| y |} = y_{| y |}$, or exists such number $r (r < | x |, r < | y |)$, that $x_1 = y_1, x_2 = y_2,..., x_r = y_r$ and $x_r + 1 > y_r + 1$. Characters in lines are compared like their ASCII codes. The input contains a single string $S$ $(1 <= | S | <= 10^5)$. It is guaranteed that string $S$ consists of only lower case Latin letters. print the lexicographically maximal string that could be obtained using these two operations. In the first test case Ayoub replaced $\"b b\"$ with $\"c\"$ so the string has been changed to $\"a c x\"$, then he swapped 'a' with 'x' so the result is $\"x c a\"$ and it is the lexicographically maximal string. ## Input The input contains a single string $S$ $(1 <= | S | <= 10^5)$.It is guaranteed that string $S$ consists of only lower case Latin letters. ## Output print the lexicographically maximal string that could be obtained using these two operations. [samples] ## Note In the first test case Ayoub replaced $\"b b\"$ with $\"c\"$ so the string has been changed to $\"a c x\"$, then he swapped 'a' with 'x' so the result is $\"x c a\"$ and it is the lexicographically maximal string.

**Definitions** Let $ S = s_1 s_2 \dots s_n $ be a string of length $ n \geq 1 $, where $ s_i \in \{a, b, \dots, z\} $ for all $ i $. **Operations** Two operations may be applied any number of times in any order: 1. **Replace**: If two consecutive characters $ s_i = s_{i+1} = c $, replace them with the next letter: $ s_i s_{i+1} \to \text{chr}(\text{ord}(c) + 1) $. 2. **Swap**: Any two adjacent characters may be swapped. **Constraints** - $ 1 \leq n \leq 10^5 $ - All characters in $ S $ are lowercase Latin letters. **Objective** Find the lexicographically maximal string obtainable from $ S $ via any sequence of the above operations.

API Response (JSON)

{
  "problem": {
    "name": "M. Two Operations",
    "description": {
      "content": "Ayoub has a string $S$ consists of only lower case Latin letters, and he wants you to make some operations on it: Ayoub wants you to make the string lexicographically maximal using the mentioned oper",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10226M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ayoub has a string $S$ consists of only lower case Latin letters, and he wants you to make some operations on it:\n\nAyoub wants you to make the string lexicographically maximal using the mentioned oper...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S = s_1 s_2 \\dots s_n $ be a string of length $ n \\geq 1 $, where $ s_i \\in \\{a, b, \\dots, z\\} $ for all $ i $.\n\n**Operations**  \nTwo operations may be applied any number of ti...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments