# Generate a String With Characters That Have Odd Counts Leetcode Solution  Difficulty Level Easy
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions String

## Problem Statement  In this problem, we are given a length. We have to generate a string that has all characters an odd number of times. For example, aaaaab is a valid string because count(a)=5 and count(b)=1.
But, aaabbc is not a valid string here because count(b)=2 which is an even number.

### Example

`n = 4`
`"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”.

`n = 2`
`"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”.

## Approach  We can use a trick here.
If the length of string is odd number then we can use a single character throughout to create the string, and if the input length is even number then we can create a string having just two characters.
One character occuring n-1 times (which will be an odd number because n is even here) and anoter character just once (which is ofcourse an odd count).

Dynamic Programming Basics

For example n=4, our output will be aaab
and if n=3, our output will be aaa we are just using characters a and b in our solution, there are more options of characters if you want.

## Implementation  ### C++ Program for Generate a String With Characters That Have Odd Counts Leetcode Solution

```#include <bits/stdc++.h>
using namespace std;

string generateTheString(int n)
{
string str;
if(n%2==0)
{
for(int i=0;i<n-1;i++)  str.push_back('a');
str.push_back('b');
}
else
{
for(int i=0;i<n;i++)  str.push_back('a');
}
return str;
}

int main()
{
int n=5;
cout<<  generateTheString(n)   << endl;
return 0;
}```
`aaaaa`

### Java Program for Generate a String With Characters That Have Odd Counts Leetcode Solution

```class Rextester
{
public static String generateTheString(int n)
{
StringBuilder sb=new StringBuilder();

if(n%2==0)
{
for(int i=0;i<n-1;i++)sb.append('a');
sb.append('b');
}
else
{
for(int i=0;i<n;i++)sb.append('a');
}

return sb.toString();
}

public static void main(String[]args)
{
int length=5;
System.out.println(generateTheString(length));
}
}```
`aaaaa`

## Complexity Analysis for Generate a String With Characters That Have Odd Counts Leetcode Solution  #### Time Complexity

O(n): We are linearly iterating for the length given to just once. Therefore, the time complextity will be O(n).

#### Space Complexity

O(n): We are creating our output string, so we are using an extra space of length given. Therefore, space complexity also is O(n).