Generate a String With Characters That Have Odd Counts — LeetCode 1374 Python Solution

The problem

Given an integer n, return a string with n characters such that each character in such string occurs an odd number of times. The returned string must contain only lowercase English letters.

Example

Input

n = 4

Output

"pppz"

Explanation

"pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".

Python solution

class Solution:
    def generateTheString(self, n: int) -> str:
        return 'a' * n if n & 1 else 'a' * (n - 1) + 'b'

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1374. Generate a String With Characters That Have Odd Counts is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems