An amusement park's turnstile scanner authenticates a visitor's wristband by reading the sequence of lowercase letters printed on it. As a tamper check, the scanner accepts a code only if, for every distinct letter that appears on the wristband, that letter's total number of occurrences is odd — this parity rule is designed to catch common single-letter-swap forgeries. The print shop needs to generate a code of an exact requested length that will pass the scanner, and, to keep its printing costs predictable, it always wants the lexicographically smallest string of lowercase letters that satisfies the rule.
Given the required length n, output the lexicographically smallest string of exactly n lowercase letters such that every distinct letter appearing in the string occurs an odd number of times.
A single line containing one integer n, the required length of the code.
A single line containing the lexicographically smallest valid code: a string of exactly n lowercase English letters in which every distinct letter used occurs an odd number of times.
Example 1
Input
4
Expected
aaab
Explanation
n=4 is even, so using all four positions for the same letter would give an even count, which fails the scanner's parity rule. The lexicographically smallest valid code instead uses three 'a's (an odd count of 3) followed by a single 'b' (an odd count of 1), giving "aaab".
Example 2
Input
1
Expected
a
Explanation
n=1 is odd, so the single letter 'a' repeated once already has an odd count (1) and satisfies the parity rule; it is trivially also the lexicographically smallest possible 1-character code.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →