Generate a String With Characters That Have Odd Counts - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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.
Approach 1: Approach 1: All Characters Same If Odd, Add One If Even
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.
Complexity
Time Complexity: O(n) due to the use of memset.
Space Complexity: O(n) for the output string.
Approach 2: Approach 2: Alternate Characters for Even `n`
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.
Complexity
Time Complexity: O(n), for iterating through the positions.
Space Complexity: O(n), for the resultant string.
Approach 3: 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Generate a String With Characters That Have Odd Counts | LeetCode • Knowledge Amplifier • 2,162 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Generate a String With Characters That Have Odd Counts easy or hard?
Generate a String With Characters That Have Odd Counts Python/Java solution
How to solve Generate a String With Characters That Have Odd Counts in O(n)?
What is the best approach for Generate a String With Characters That Have Odd Counts?
Is Generate a String With Characters That Have Odd Counts asked at Google/Amazon/Meta?
What data structure is used in Generate a String With Characters That Have Odd Counts?
What is the time complexity of Generate a String With Characters That Have Odd Counts?
Ready to solve this problem?
Practice Generate a String With Characters That Have Odd Counts with our built-in code editor and test cases.
Practice on FleetCode