A. Letters Cyclic Shift

Codeforces

IDCF708A

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgreedyimplementationstrings

English · Original

Chinese · Translation

Formal · Original

You are given a non-empty string _s_ consisting of lowercase English letters. You have to pick **exactly one non-empty substring** of _s_ and shift all its letters '_z_' '_y_' '_x_' '_b_' '_a_' '_z_'. In other words, each character is replaced with the previous character of English alphabet and '_a_' is replaced with '_z_'. What is the lexicographically minimum string that can be obtained from _s_ by performing this shift exactly once? ## Input The only line of the input contains the string _s_ (1 ≤ |_s_| ≤ 100 000) consisting of lowercase English letters. ## Output Print the lexicographically minimum string that can be obtained from _s_ by shifting letters of exactly one non-empty substring. [samples] ## Note String _s_ is lexicographically smaller than some other string _t_ of the same length if there exists some 1 ≤ _i_ ≤ |_s_|, such that _s_1 = _t_1, _s_2 = _t_2, ..., _s__i_ - 1 = _t__i_ - 1, and _s__i_ < _t__i_.

给定一个非空字符串 #cf_span[s]，由小写英文字母组成。你需要恰好选择一个非空子串，并将其中所有字母进行如下变换：'_z_' 变为 '_y_'，'_y_' 变为 '_x_'，……，'_b_' 变为 '_a_'，'_a_' 变为 '_z_'。换句话说，每个字符被替换为英文字母表中的前一个字母，'_a_' 被替换为 '_z_'。通过恰好执行一次这样的变换，你能得到的字典序最小的字符串是什么？输入的唯一一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100 000]），由小写英文字母组成。请输出通过恰好对一个非空子串进行上述变换后能得到的字典序最小的字符串。字符串 #cf_span[s] 的字典序小于另一个相同长度的字符串 #cf_span[t]，当且仅当存在某个 #cf_span[1 ≤ i ≤ |s|]，使得 #cf_span[s1 = t1, s2 = t2, ..., si - 1 = ti - 1]，且 #cf_span[si < ti]。 ## Input 输入的唯一一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100 000]），由小写英文字母组成。 ## Output 请输出通过恰好对一个非空子串进行上述变换后能得到的字典序最小的字符串。 [samples] ## Note 字符串 #cf_span[s] 的字典序小于另一个相同长度的字符串 #cf_span[t]，当且仅当存在某个 #cf_span[1 ≤ i ≤ |s|]，使得 #cf_span[s1 = t1, s2 = t2, ..., si - 1 = ti - 1]，且 #cf_span[si < ti]。

**Definitions** Let $ s \in \Sigma^n $ be a string of length $ n \geq 1 $, where $ \Sigma = \{a, b, \dots, z\} $ is the set of lowercase English letters. Define the *shift operation* $ \sigma: \Sigma \to \Sigma $ as: $$ \sigma(c) = \begin{cases} z & \text{if } c = a \\ \text{prev}(c) & \text{otherwise} \end{cases} $$ where $ \text{prev}(c) $ is the preceding letter in the alphabet (e.g., $ \text{prev}(b) = a $, $ \text{prev}(z) = y $). Let $ s[i:j] $ denote the substring of $ s $ from index $ i $ to $ j $ (inclusive), with $ 1 \leq i \leq j \leq n $. **Constraints** 1. $ 1 \leq n \leq 100{,}000 $ 2. $ s \in \Sigma^n $, all characters are lowercase English letters. 3. Exactly one non-empty contiguous substring must be shifted. **Objective** Find the lexicographically smallest string $ s' $ obtainable by selecting exactly one non-empty substring $ s[i:j] $ and replacing each character $ c \in s[i:j] $ with $ \sigma(c) $, while leaving all other characters unchanged. That is, $$ s' = s[1:i-1] + \sigma(s[i:j]) + s[j+1:n] $$ for some $ 1 \leq i \leq j \leq n $, and we seek: $$ \arg\min_{1 \leq i \leq j \leq n} s' $$ lexicographically.

Samples

Input #1

codeforces

Output #1

bncdenqbdr

Input #2

abacaba

Output #2

aaacaba

API Response (JSON)

{
  "problem": {
    "name": "A. Letters Cyclic Shift",
    "description": {
      "content": "You are given a non-empty string _s_ consisting of lowercase English letters. You have to pick **exactly one non-empty substring** of _s_ and shift all its letters '_z_' '_y_' '_x_' '_b_' '_a_' '_z_'.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF708A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a non-empty string _s_ consisting of lowercase English letters. You have to pick **exactly one non-empty substring** of _s_ and shift all its letters '_z_' '_y_' '_x_' '_b_' '_a_' '_z_'....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个非空字符串 #cf_span[s]，由小写英文字母组成。你需要恰好选择一个非空子串，并将其中所有字母进行如下变换：'_z_' 变为 '_y_'，'_y_' 变为 '_x_'，……，'_b_' 变为 '_a_'，'_a_' 变为 '_z_'。换句话说，每个字符被替换为英文字母表中的前一个字母，'_a_' 被替换为 '_z_'。\n\n通过恰好执行一次这样的变换，你能得到的字典序最小的字符串是什么...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^n $ be a string of length $ n \\geq 1 $, where $ \\Sigma = \\{a, b, \\dots, z\\} $ is the set of lowercase English letters.  \nDefine the *shift operation* $ \\sigma: \\Si...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments