codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1781C.md (2341B)


      1 Source: https://codeforces.com/problemset/problem/1781/C
      2 
      3 C. Equal Frequencies
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Let's call a string balanced if all characters that are present in it appear the same number of times. For example, "coder", "appall", and "ttttttt" are balanced, while "wowwow" and "codeforces" are not.
     22 
     23 You are given a string $s$ of length $n$ consisting of lowercase English letters. Find a balanced string $t$ of the same length $n$ consisting of lowercase English letters that is different from the string $s$ in as few positions as possible. In other words, the number of indices $i$ such that $s_i \ne t_i$ should be as small as possible.
     24 
     25 Input
     26 
     27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     28 
     29 Each test case consists of two lines. The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the string $s$.
     30 
     31 The second line contains the string $s$ of length $n$ consisting of lowercase English letters.
     32 
     33 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     34 
     35 Output
     36 
     37 For each test case, print the smallest number of positions where string $s$ and a balanced string $t$ can differ, followed by such a string $t$.
     38 
     39 If there are multiple solutions, print any. It can be shown that at least one balanced string always exists.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 5
     49 
     50 hello
     51 
     52 10
     53 
     54 codeforces
     55 
     56 5
     57 
     58 eevee
     59 
     60 6
     61 
     62 appall
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 helno
     70 2
     71 codefofced
     72 1
     73 eeeee
     74 0
     75 appall
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, the given string "hello" is not balanced: letters 'h', 'e', and 'o' appear in it once, while letter 'l' appears twice. On the other hand, string "helno" is balanced: five distinct letters are present in it, and each of them appears exactly once. Strings "hello" and "helno" differ in just one position: the fourth character. Other solutions are possible too.
     81 
     82 In the second test case, string "codefofced" is balanced since only letters 'c', 'o', 'd', 'e', and 'f' are present in it, and each of them appears exactly twice.
     83 
     84 In the third test case, string "eeeee" is balanced since only letter 'e' is present in it.
     85 
     86 In the fourth test case, the given string "appall" is already balanced.