F. Exchange

Codeforces

IDCF10110F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Given a string of lowercase English letters. You are allowed to choose two letters that exist in any position in the string, replace all occurrences of the first letter you chose with the second one, and replace all occurrences of the second letter you chose with the first one. Your task is to find the string that comes first in dictionary order among all possible strings that you can get by performing the above operation *at most once*. For example, by exchanging letter ‘a’ with letter ‘h’ in string “hamza”, we can get string “ahmzh”. The first line of input contains a single integer T, the number of test cases. Each test case contains a non-empty string on a single line that contains no more than 105 lowercase English letters. For each test case, print the required string on a single line. ## Input The first line of input contains a single integer T, the number of test cases.Each test case contains a non-empty string on a single line that contains no more than 105 lowercase English letters. ## Output For each test case, print the required string on a single line. [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. Let $ S = (s_1, s_2, \dots, s_n) $ be a string of length $ n \geq 1 $, where each $ s_i \in \{a, b, \dots, z\} $. **Constraints** 1. $ 1 \leq t \leq 1000 $ 2. For each test case: $ 1 \leq n \leq 10^5 $ **Operation** For any pair of distinct letters $ x, y \in \{a, \dots, z\} $, define the transposition $ T_{x,y}(S) $ as the string obtained by swapping all occurrences of $ x $ and $ y $ in $ S $. Let $ \mathcal{O}(S) = \{ S \} \cup \{ T_{x,y}(S) \mid x, y \in \text{alph}(S), x \neq y \} $, where $ \text{alph}(S) $ is the set of distinct characters in $ S $. **Objective** For each test case, output the lexicographically minimal string in $ \mathcal{O}(S) $.

API Response (JSON)

{
  "problem": {
    "name": "F. Exchange",
    "description": {
      "content": "Given a string of lowercase English letters. You are allowed to choose two letters that exist in any position in the string, replace all occurrences of the first letter you chose with the second one, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10110F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a string of lowercase English letters. You are allowed to choose two letters that exist in any position in the string, replace all occurrences of the first letter you chose with the second one, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a string of length $ n \\geq 1 $, where each $ s_i \\in \\{a, b, \\dots, z\\} $.  \n\n**Constra...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments