問題一覧 > 通常問題

No.1609 String Division Machine

レベル : / AI推定難易度 : 2025 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 36
作問者 : SPD_9X2 / テスター : 👑 tute7627 penguinman
お気に入りにしたユーザー ProblemId : 6470 / 自分の提出
問題文最終更新日: 2021-07-14 17:30:38
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 304 (順位表) の他の問題:

Problem Statement

A string division machine takes a string $T$ as input, divides $T$ into several subsequences according to the following algorithm, and outputs them.

  1. Among the subsequences of $T$, choose the lexicographically largest one. It can be proved that this is uniquely determined, including the chosen positions.
  2. Output the chosen subsequence and delete it from $T$.
  3. If $T$ is an empty string, terminate. Otherwise, go back to $1$.

We call the number of output subsequences the string division number of the string $T$. (The string division number is equal to the number of times step 2. of the above algorithm is executed.)


You are given a string $S$ consisting of lowercase English letters and "?".

Among the strings obtained by replacing every "?" in $S$ with an arbitrary lowercase English letter, find one with the minimum string division number. (Each "?" can be independently replaced with any lowercase English letter.)

If there are multiple such strings, find the lexicographically smallest one.


Here, a subsequence of a string $T$ refers to a string obtained by choosing $1$ or more characters from $T$ and concatenating them in their original order.

Input

$S$

  • $S$ is a string consisting of lowercase English letters and "?".
  • The end of $S$ is indicated by a newline character.
  • $1 \le |S| \le 10^5$

Output

Output the answer in one line ($1$ line). Print a newline at the end.

Sample

Sample 1
Input
?c?b?d?
Output
ccbbada

$T$ changes as ccbbada → ccbba → empty string, and is divided into $2$ subsequences: da and ccbba.
There is no way to make the string division number less than $2$, and among the strings with string division number $2$ that can be made from $S$, none is lexicographically smaller than ccbbada, so output ccbbada.

Sample 2
Input
????
Output
aaaa

$T$ changes as aaaa → empty string, and is divided into $1$ subsequence: aaaa.

Sample 3
Input
?yzab
Output
yyzab
Sample 4
Input
?yzabc
Output
ayzabc
Sample 5
Input
?yz?xyz?tu?def?abc?
Output
xyzxxyzdtuddefaabca

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。