Question

1374. Generate a String With Characters That Have Odd Counts

中文文档

Description

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.  

 

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

Solutions

Solution 1: Construction

If $n$ is odd, then we can directly construct a string with $n$ 'a' characters.

If $n$ is even, then we can construct a string with $n-1$ 'a' characters and $1$ 'b' character.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string.

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

class Solution {
  public String generateTheString(int n) {
    return (n % 2 == 1) ? "a".repeat(n) : "a".repeat(n - 1) + "b";
  }
}

class Solution {
public:
  string generateTheString(int n) {
    string ans(n, 'a');
    if (n % 2 == 0) {
      ans[0] = 'b';
    }
    return ans;
  }
};

func generateTheString(n int) string {
  ans := strings.Repeat("a", n-1)
  if n%2 == 0 {
    ans += "b"
  } else {
    ans += "a"
  }
  return ans
}

function generateTheString(n: number): string {
  const ans = Array(n).fill('a');
  if (n % 2 === 0) {
    ans[0] = 'b';
  }
  return ans.join('');
}