Generate a String With Characters That Have Odd Counts Leetcode Solution  

Difficulty Level Easy
Frequently asked in DiDi
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:

Please click Like if you loved this article?

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

See also
Dynamic Programming Basics

For example n=4, our output will be aaab
and if n=3, our output will be aaa

Generate a String With Characters That Have Odd Counts Leetcode SolutionPin
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).

Please click Like if you loved this article?

1