1374. Generate a String With Characters That Have Odd Counts

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. If there are multiples valid strings, return any of them.

https://leetcode.com/problems/generate-a-string-with-characters-that-have-odd-counts/

Example 1:

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".

Example 2:

Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".

Example 3:

Input: n = 7
Output: "holasss"

Constraints:

• 1 <= n <= 500

Test Cases

1
2

class Solution:
    def generateTheString(self, n: int) -> str:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from typing import Counter
import pytest

from solution import Solution


@pytest.mark.parametrize('n, expected', [
    (4, "pppz"),
    (2, "xy"),
    (7, "holasss"),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, n, expected):
    res = sol.generateTheString(n)
    if res != expected:
        assert len(res) == n
        counts = Counter(res)
        remains = [freq & 1 for freq in counts.values()]
        assert remains == [1] * len(counts)

Thoughts

如果 n 是奇数，直接用 n 个任意字母（如 'a'）拼成字符串。否则可以用 n - 1 个任意字母（如 'a'）再加任意另外一个字母（如 'b'）即可。

Code

1
2
3

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

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章