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 <= 500Problem Overview: You need to construct any string of length n such that every character in the string appears an odd number of times. The characters can be any lowercase letters. The only constraint is that the frequency of each character must be odd.
Approach 1: All Characters Same If Odd, Add One If Even (O(n) time, O(1) space)
The key observation is that a string containing the same character repeated n times automatically satisfies the requirement when n is odd. If n is even, that repetition would produce an even count, which violates the rule. To fix this, generate n-1 copies of one character (for example 'a') and append a different character like 'b'. Now the counts become n-1 and 1, both odd numbers. The algorithm simply checks whether n is even or odd and constructs the string accordingly using basic string operations.
Approach 2: Alternate Characters for Even n (O(n) time, O(1) space)
Another valid construction uses two characters when n is even. Fill most of the string with one character and ensure both characters end up with odd frequencies. For example, repeat 'a' for n-1 positions and place 'b' once. This approach highlights the same insight from a slightly different perspective: only the parity of counts matters. As long as each character appears an odd number of times, the exact arrangement of characters is irrelevant. Implementation still involves a single pass string build using simple string construction techniques.
Recommended for interviews: Approach 1 is what interviewers expect. It shows you recognized the parity trick immediately and avoided unnecessary complexity. Many candidates overthink this problem with frequency maps or multiple characters. Demonstrating the simple observation that n odd → repeat one character, n even → split into n-1 and 1 shows strong reasoning with basic string manipulation.
If n is odd, create a string of the same character repeated n times for optimal solution. If n is even, use one character repeated n-1 times and another character to ensure all occurrences are odd.
This solution allocates memory for a string of length n and fills it with 'a'. If n is even, the last character is replaced with 'b'. This ensures all characters appear an odd number of times. The string is terminated with a null character.
Time Complexity: O(n) due to the use of memset.
Space Complexity: O(n) for the output string.
For an even n, create the string by alternating two different characters such that all characters always have odd frequencies. This guarantees one of the many valid configurations.
This implementation cycles between 'a' and 'b' for each position. For even n, the last character is set to 'c' to ensure an odd frequency for each character.
Time Complexity: O(n), for iterating through the positions.
Space Complexity: O(n), for the resultant string.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: All Characters Same If Odd, Add One If Even | Time Complexity: O(n) due to the use of |
| Approach 2: Alternate Characters for Even `n` | Time Complexity: O(n), for iterating through the positions. |
| Construction | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| All Characters Same If Odd, Add One If Even | O(n) | O(1) | Best general solution. Minimal logic and optimal for interviews. |
| Alternate Characters for Even n | O(n) | O(1) | Useful to demonstrate parity reasoning using two characters when n is even. |
Generate a String With Characters That Have Odd Counts | LeetCode • Knowledge Amplifier • 2,162 views views
Watch 9 more video solutions →Practice Generate a String With Characters That Have Odd Counts with our built-in code editor and test cases.
Practice on FleetCode