Generate a String With Characters That Have Odd Counts Leetcode Solution


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

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions