Easy

题目描述

给你一个整数 n，请你返回一个含 n 个字符的字符串，其中每种字符在该字符串中都恰好出现奇数次。

返回的字符串必须只含有小写英文字母。如果存在多个满足题目要求的字符串，则可以返回其中任意一个。

示例 1：

输入：n = 4
输出："pppz"
解释："pppz" 是一个满足题目要求的字符串，因为 'p' 出现了三次，且 'z' 出现了一次。注意，还有很多其他满足题目要求的字符串，诸如 "ohhh" 和 "love"。

示例 2：

输入：n = 2
输出："xy"
解释："xy" 是一个满足题目要求的字符串，因为 'x' 和 'y' 各出现了一次。注意，还有很多其他满足题目要求的字符串，诸如 "ag" 和 "ur"。

示例 3：

输入：n = 7
输出："holasss"

提示：

  • 1 <= n <= 500

解题思路

这道题的核心在于理解什么样的字符组合能够满足"每种字符都恰好出现奇数次"的要求。

思路分析：

最直观的解法是根据 n 的奇偶性来构造字符串：

  1. 当 n 为奇数时：我们可以用 n 个相同的字符（如 ‘a’）来构成字符串，因为 n 本身就是奇数。

  2. 当 n 为偶数时：我们不能只用一种字符，因为偶数个相同字符不满足要求。但我们可以用 n-1 个字符 ‘a’ 和 1 个字符 ‘b’，这样 ‘a’ 出现 n-1（奇数）次，‘b’ 出现 1（奇数）次。

为什么这样可行？

  • 奇数 + 奇数 = 偶数
  • 偶数 + 奇数 = 奇数

所以当 n 为偶数时，我们需要至少两种字符，且每种字符的出现次数都是奇数，这样总和才能是偶数。

推荐解法：基于奇偶性的简单构造方法，时间复杂度最优且代码简洁。

代码实现

class Solution {
public:
    string generateTheString(int n) {
        if (n % 2 == 1) {
            return string(n, 'a');
        } else {
            return string(n - 1, 'a') + 'b';
        }
    }
};

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

public class Solution {
    public string GenerateTheString(int n) {
        if (n % 2 == 1) {
            return new string('a', n);
        } else {
            return new string('a', n - 1) + 'b';
        }
    }
}

/**
 * @param {number} n
 * @return {string}
 */
var generateTheString = function(n) {
    if (n % 2 === 1) {
        return 'a'.repeat(n);
    } else {
        return 'a'.repeat(n - 1) + 'b';
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
奇偶性构造O(n)O(1)

说明：

  • 时间复杂度：O(n)，需要构造长度为 n 的字符串
  • 空间复杂度：O(1)，除了返回结果外，只使用常数额外空间