Generate a String With Characters That Have Odd Counts Leetcode Solution

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).

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).