Generate a String with Characters That Have Odd Counts in Java

Given an integer n, the task is to find a string of length n where every character appears an odd number of times. If n is odd, we can simply use one character, while if n is even, we can adjust one character to ensure all have odd frequencies.

Example 1:

Input: n = 7

Output: aaaaabc

Explanation: 'a' appears 5 times, 'b' and 'c' appear once, ensuring all characters have odd frequencies.

Example 2:

Input: n = 5

Output: aaabc

Explanation: 'a' appears 3 times, 'b' and 'c' appear once, ensuring all characters have odd frequencies.

Example 3:

Input: n = 3

Output: abc

Explanation: Each character 'a', 'b', and 'c' appears once, ensuring all characters have odd frequencies.

Approach 1: Using a Single Character (Odd n)

The approach generates a string of length n where all characters appear an odd number of times. Since n itself is odd, using a single character (e.g., "a") repeated n times ensures that it appears an odd number of times.

Algorithm

Step 1: Use the Java 11+ method .repeat(n) to generate a string of length n consisting of the character 'a'.

Step 2: If n is odd, the string automatically satisfies the condition where all characters appear an odd number of times.

Step 3: Return the generated string.

Output:

 
aaaaa   

Time Complexity: The time complexity of a program is O(n). This is because constructing a string of length n requires O(n) time.

Space Complexity: The space complexity of a program is O(n). This is because the generated string takes n space in memory.

Approach 2: Using Multiple Characters

The approach constructs a string of length n such that every character appears an odd number of times. It uses three characters ('a', 'b', and 'c') to ensure all frequencies remain odd.

Algorithm

Step 1: Initialize an empty StringBuilder.

Step 2: Append 'a' (n-2) times to the string.

Step 3: Append 'b' once and 'c' once to ensure all characters have an odd count.

Step 4: Return the constructed string.

Output:

 
aaaaabc   

Time Complexity: The time complexity of a program is O(n). This is because constructing a string of length n requires O(n) time.

Space Complexity: The space complexity of a program is O(n). This is because the generated string takes n space in memory.