C. String Transformation

Codeforces

IDCF946C

Time1000ms

Memory256MB

Difficulty—

greedystrings

English · Original

Chinese · Translation

Formal · Original

You are given a string _s_ consisting of |_s_| small english letters. In one move you can replace any character of this string to the next character in alphabetical order (_a_ will be replaced with _b_, _s_ will be replaced with _t_, etc.). You cannot replace letter _z_ with any other letter. Your target is to make some number of moves (not necessary minimal) to get string _abcdefghijklmnopqrstuvwxyz_ (english alphabet) as a subsequence. Subsequence of the string is the string that is obtained by deleting characters at some positions. You need to print the string that will be obtained from the given string and will be contain english alphabet as a subsequence or say that it is impossible. ## Input The only one line of the input consisting of the string _s_ consisting of |_s_| (1 ≤ |_s_| ≤ 105) small english letters. ## Output If you can get a string that can be obtained from the given string and will contain english alphabet as a subsequence, print it. Otherwise print «-1» (without quotes). [samples]

你被给定一个由 #cf_span[|s|] 个小写英文字母组成的字符串 #cf_span[s]。在一次操作中，你可以将该字符串中的任意字符替换为字母表中的下一个字符（_a_ 会被替换为 _b_，_s_ 会被替换为 _t_，依此类推）。你不能将字母 _z_ 替换为任何其他字母。你的目标是进行若干次操作（不要求最少）以使字符串 _abcdefghijklmnopqrstuvwxyz_（英文字母表）成为其子序列。字符串的子序列是指通过在某些位置删除字符后得到的字符串。你需要输出从给定字符串经过操作后得到的字符串，该字符串需包含英文字母表作为子序列；若不可能，则输出 -1。输入仅一行，包含一个由 #cf_span[|s|]（#cf_span[1 ≤ |s| ≤ 105]）个小写英文字母组成的字符串 #cf_span[s]。如果你能得到一个从给定字符串经过操作后得到的、且包含英文字母表作为子序列的字符串，请输出它；否则输出 «-1»（不含引号）。 ## Input 输入仅一行，包含一个由 #cf_span[|s|]（#cf_span[1 ≤ |s| ≤ 105]）个小写英文字母组成的字符串 #cf_span[s]。 ## Output 如果你能得到一个从给定字符串经过操作后得到的、且包含英文字母表作为子序列的字符串，请输出它；否则输出 «-1»（不含引号）。 [samples]

**Definitions** Let $ s \in \{a, b, \dots, z\}^* $ be the input string of length $ n = |s| $, with $ 1 \leq n \leq 10^5 $. Let $ \Sigma = \texttt{"abcdefghijklmnopqrstuvwxyz"} $ be the target alphabet string of length 26. **Constraints** 1. Each character in $ s $ is a lowercase English letter. 2. In one move, a character $ c \in s $ (where $ c \neq \texttt{z} $) can be replaced by the next character in alphabetical order: $ c \to \texttt{next}(c) $, where $ \texttt{next}(a)=b, \dots, \texttt{next}(y)=z $. 3. Character $ \texttt{z} $ cannot be changed. 4. The resulting string must contain $ \Sigma $ as a subsequence. **Objective** Find a string $ s' $, obtainable from $ s $ via any number of allowed moves, such that $ \Sigma $ is a subsequence of $ s' $. If such $ s' $ exists, output any such $ s' $; otherwise, output $-1$.

Samples

Input #1

aacceeggiikkmmooqqssuuwwyy

Output #1

abcdefghijklmnopqrstuvwxyz

Input #2

thereisnoanswer

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. String Transformation",
    "description": {
      "content": "You are given a string _s_ consisting of |_s_| small english letters. In one move you can replace any character of this string to the next character in alphabetical order (_a_ will be replaced with _",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF946C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string _s_ consisting of |_s_| small english letters.\n\nIn one move you can replace any character of this string to the next character in alphabetical order (_a_ will be replaced with _...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个由 #cf_span[|s|] 个小写英文字母组成的字符串 #cf_span[s]。\n\n在一次操作中，你可以将该字符串中的任意字符替换为字母表中的下一个字符（_a_ 会被替换为 _b_，_s_ 会被替换为 _t_，依此类推）。你不能将字母 _z_ 替换为任何其他字母。\n\n你的目标是进行若干次操作（不要求最少）以使字符串 _abcdefghijklmnopqrstuvwxyz_（英文字母...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{a, b, \\dots, z\\}^* $ be the input string of length $ n = |s| $, with $ 1 \\leq n \\leq 10^5 $.  \nLet $ \\Sigma = \\texttt{\"abcdefghijklmnopqrstuvwxyz\"} $ be the target alph...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments