Generate a String With Characters That Have Odd Counts solution and explanation
Google
9 more videos on this problem
Generate a String With Characters That Have Odd Counts | LeetCodeKnowledge Amplifier · 5:39 · 2K views
1374. Generate a String With Characters That Have Odd Counts || Leetcode weekly contest 179code Explainer · 2:38 · 485 views
LeetCode#1374 Generate a String With Characters That Have Odd Counts - PythonCodeJulian · 1:00 · 476 views
leetcode - 1374 Generate a String With Characters That Have Odd Counts Solution w/ ExplanationlitCode · 9:20 · 335 views
Leetcode Solution - 1374 Generate a String With Characters That Have Odd CountsJohn Leonardo · 2:58 · 330 views
[LeetCode] 1374. Generate a String With Characters That Have Odd Counts - Coding solutionRiyafa Abdul Hameed · 9:09 · 327 views
LeetCode 1374 | Generate a String with Characters That Have Odd Counts #100daysofcoding #coderslifeTRIKX · 1:01 · 306 views
1374 Generate a String With Characters That Have Odd Counts | Complete Playlist of Easy Level Ques.EduEverybody · 9:04 · 180 views
1374 Generate a String With Characters That Have Odd Counts - Leetcode in Go - StringXavier Xie · 3:10 · 168 views
Generate a String With Characters That Have Odd Counts | Leetcode # 1374 | EasyMorning Byte · 2:33 · 167 views
The 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.
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.
def generateString(n):
if n % 2 == 0:
return 'a' * (n - 1) + 'b'
else:
return 'a' * n
n = 4
print(generateString(n))public class GenerateString {
public static String generateString(int n) {
if (n % 2 == 0) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n - 1; i++) sb.append('a');
sb.append('b');
return sb.toString();
} else {
return "a".repeat(n);
}
}
public static void main(String[] args) {
int n = 4;
System.out.println(generateString(n));
}
}#include <iostream>
#include <string>
std::string generateString(int n) {
if (n % 2 == 0)
return std::string(n - 1, 'a') + 'b';
else
return std::string(n, 'a');
}
int main() {
int n = 4;
std::string result = generateString(n);
std::cout << result << std::endl;
return 0;
}function generateString(n) {
if (n % 2 === 0) {
return 'a'.repeat(n - 1) + 'b';
} else {
return 'a'.repeat(n);
}
}
let n = 4;
console.log(generateString(n));#include <stdio.h>
#include <string.h>
char* generateString(int n) {
char* result = (char*)malloc(n + 1);
if (n % 2 == 0) {
memset(result, 'a', n - 1);
result[n - 1] = 'b';
} else {
memset(result, 'a', n);
}
result[n] = '\0';
return result;
}
int main() {
int n = 4;
char* result = generateString(n);
printf("%s\n", result);
free(result);
return 0;
}using System;
public class GenerateStringExample {
public static string GenerateString(int n) {
if (n % 2 == 0) {
return new string('a', n - 1) + 'b';
} else {
return new string('a', n);
}
}
public static void Main() {
int n = 4;
Console.WriteLine(GenerateString(n));
}
}This Python function checks if n is even, creating a string with 'a's and appending a 'b' to ensure odd frequency of characters.
Time Complexity: O(n), due to string multiplication.
Space Complexity: O(n).
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.
def generateString(n):
s = ''.join(['a' if i % 2 == 0 else 'b' for i in range(n)])
if n % 2 == 0:
s = s[:-1] + 'c'
return s
n = 4
print(generateString(n))public class GenerateStringAlt {
public static String generateString(int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(i % 2 == 0 ? 'a' : 'b');
}
if (n % 2 == 0) sb.setCharAt(n - 1, 'c');
return sb.toString();
}
public static void main(String[] args) {
int n = 4;
System.out.println(generateString(n));
}
}#include <iostream>
#include <string>
std::string generateString(int n) {
std::string result;
for (int i = 0; i < n; ++i) {
result += (i % 2 == 0) ? 'a' : 'b';
}
if (n % 2 == 0) result[n - 1] = 'c';
return result;
}
int main() {
int n = 4;
std::cout << generateString(n) << std::endl;
return 0;
}function generateString(n) {
let result = '';
for (let i = 0; i < n; i++) {
result += (i % 2 === 0) ? 'a' : 'b';
}
if (n % 2 === 0) result = result.slice(0, -1) + 'c';
return result;
}
let n = 4;
console.log(generateString(n));#include <stdio.h>
#include <stdlib.h>
char* generateString(int n) {
char* result = (char*)malloc(n + 1);
for (int i = 0; i < n; i++) {
result[i] = (i % 2) ? 'b' : 'a';
}
if (n % 2 == 0) result[n-1] = 'c';
result[n] = '\0';
return result;
}
int main() {
int n = 4;
char* result = generateString(n);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Text;
public class GenerateStringAlt {
public static string GenerateString(int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.Append((i % 2 == 0) ? 'a' : 'b');
}
if (n % 2 == 0) sb[n - 1] = 'c';
return sb.ToString();
}
public static void Main() {
int n = 4;
Console.WriteLine(GenerateString(n));
}
}In Python, the solution builds a string by alternating between 'a' and 'b'. If n is even, the last character is replaced with 'c' to meet the requirements.
Time Complexity: O(n).
Space Complexity: O(n).
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.
function generateTheString(n: number): string {
const ans = Array(n).fill('a');
if (n % 2 === 0) {
ans[0] = 'b';
}
return ans.join('');
}func generateTheString(n int) string {
ans := strings.Repeat("a", n-1)
if n%2 == 0 {
ans += "b"
} else {
ans += "a"
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: All Characters Same If Odd, Add One If Even | Time Complexity: O(n), due to string multiplication. |
| Approach 2: Alternate Characters for Even `n` | Time Complexity: O(n). |
| Construction | – |
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. |
Frequently asked questions
Is Generate a String With Characters That Have Odd Counts easy or hard?
The problem is classified as Easy on LeetCode with a high acceptance rate around 78%. The main challenge is recognizing that only the parity of character counts matters, which leads to a simple greedy construction.
Generate a String With Characters That Have Odd Counts Python/Java solution
In Python or Java, check if n is odd. If it is, return 'a' repeated n times. If n is even, return 'a' repeated n-1 times followed by 'b'. Both implementations run in O(n) time and use constant auxiliary space.
How to solve Generate a String With Characters That Have Odd Counts in O(n)?
Check the parity of n. If n is odd, generate a string like "aaaa..." with n repetitions of the same character. If n is even, generate n-1 copies of 'a' and append 'b'. Both character frequencies become odd, and the construction takes linear time.
What is the best approach for Generate a String With Characters That Have Odd Counts?
The optimal approach checks whether n is odd or even. If n is odd, return a string with the same character repeated n times. If n is even, return n-1 copies of one character and one copy of another character. This guarantees both counts are odd and runs in O(n) time with O(1) extra space.
Is Generate a String With Characters That Have Odd Counts asked at Google/Amazon/Meta?
This problem is categorized as an easy string construction question and appears in coding practice sets used by companies like Amazon and Google for warm-up or screening rounds. It tests logical reasoning about parity rather than complex algorithms.
What data structure is used in Generate a String With Characters That Have Odd Counts?
The solution primarily uses basic string construction. No advanced data structures such as hash maps or arrays are required because the parity trick allows a direct construction with one or two characters.
What is the time complexity of Generate a String With Characters That Have Odd Counts?
The time complexity is O(n) because the algorithm constructs a string of length n. Each character is appended once during the build process. The space complexity is O(1) beyond the output string since only a few variables are used.