# Generate a String With Characters That Have Odd Counts
**Difficulty:** EASY
[External](https://leetcode.com/problems/generate-a-string-with-characters-that-have-odd-counts)
Canonical: https://scaleengineer.com/dsa/problems/generate-a-string-with-characters-that-have-odd-counts
**Data structures:** String
---
## Problem
Given an integer `n`, _return a string with `n` characters such that each character in such string occurs **an odd number of times**_.

The returned string must contain only lowercase English letters. If there are multiples valid strings, return **any** of them. 

**Example 1:**

**Input:** n = 4
**Output:** "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".

**Example 2:**

**Input:** n = 2
**Output:** "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".

**Example 3:**

**Input:** n = 7
**Output:** "holasss"

**Constraints:**

* `1 <= n <= 500`

# Approaches
## Backtracking Search
This approach involves exploring all possible combinations of characters to form a string of length `n`. We use a recursive function to build the string character by character. At the end, once a string of length `n` is formed, we check if it satisfies the condition that all character counts are odd. While this approach is guaranteed to find a solution, it is highly inefficient due to the vast number of possibilities it explores.
**Time:** O(26^n). For each of the `n` positions in the string, we have 26 choices of characters. This leads to an exponential number of paths to explore, making it impractical for all but the smallest values of `n`. · **Space:** O(n). The maximum depth of the recursion is `n`. Additionally, we need O(26) or O(1) space to store the character counts. Thus, the space complexity is dominated by the recursion stack.
**Pros:** It is a generic problem-solving technique that can, in theory, find a solution for any similar constraint satisfaction problem.
**Cons:** Extremely inefficient with exponential time complexity.; Impractical for the given constraints (`1 <= n <= 500`).; Overly complex to implement for such a simple problem.
### Explanation
This method attempts to find a solution by systematically trying all possibilities. It's a brute-force method that is too slow for the given constraints but illustrates a general-purpose problem-solving strategy.

We can define a recursive function that tries to place a character at each position from `0` to `n-1`. After placing `n` characters, it checks if the resulting string is valid. If not, it backtracks and tries a different character.

Because this approach is computationally infeasible (`O(26^n)`), a full implementation would time out on any platform. It serves as a theoretical baseline for a 'worst-case' algorithm.
### Algorithm
- Define a recursive function `findValidString(index, charCounts)` that tries to build a valid string.
- `index` is the current position in the string to fill (from 0 to n-1).
- `charCounts` is an array of size 26 to store frequencies.
- **Base Case**: If `index == n`:
    - Check if all non-zero counts in `charCounts` are odd.
    - If true, construct the string from `charCounts` and return it.
    - If false, return a special value indicating no solution found from this path (e.g., null).
- **Recursive Step**:
    - Iterate through characters `c` from 'a' to 'z'.
    - Increment count for `c` in `charCounts`.
    - Call `findValidString(index + 1, charCounts)`.
    - If the call returns a valid string, return it immediately.
    - Decrement count for `c` (backtrack).
- If the loop finishes without finding a solution, return null.
- The initial call would be `findValidString(0, new int[26])`.

## Simple Constructive Approach
This is a highly efficient and straightforward approach that constructs a valid string directly based on the parity of `n`. By analyzing the properties of odd and even numbers, we can find a simple pattern to generate a valid string in linear time.
**Time:** O(n). We iterate up to `n` times to build the string. Operations like `StringBuilder.append`, `Arrays.fill`, and the `String` constructor all take time proportional to the length of the string being created. · **Space:** O(n). We need to allocate memory for the resulting string of length `n`. If the output string is not counted towards space complexity, it would be O(1) as we only use a few variables.
**Pros:** Optimal time and space complexity.; Very simple to understand and implement.; Handles all cases within the given constraints efficiently.
**Cons:** There are no significant disadvantages to this approach for this particular problem.
### Explanation
The core idea is to satisfy the odd-count condition using the minimum number of distinct characters. We consider two cases based on whether `n` is odd or even.

**Case 1: `n` is odd.**
If we use only one character, say 'a', and repeat it `n` times, its count will be `n`. Since `n` is odd, this satisfies the condition. For example, for `n=5`, the string `"aaaaa"` is a valid solution.

**Case 2: `n` is even.**
If we use one character, its count would be `n` (even), which is not allowed. We need at least two characters. Let their counts be `c1` and `c2`. We need `c1` and `c2` to be odd, and `c1 + c2 = n`. The sum of two odd numbers is always even, so this is a valid strategy. We can choose the simplest odd numbers: `1` and `n-1`. Since `n` is even, `n-1` is guaranteed to be odd. So, we can construct a string with `n-1` occurrences of one character (e.g., 'a') and `1` occurrence of another character (e.g., 'b'). For example, for `n=4`, the string `"aaab"` is a valid solution (3 'a's, 1 'b').

This logic covers all possible values of `n` and provides a simple way to construct the string. Here are two ways to implement this in Java:

**Implementation using `StringBuilder`:**
```java
class Solution {
    public String generateTheString(int n) {
        StringBuilder sb = new StringBuilder(n);
        if (n % 2 == 1) {
            // If n is odd, use one character 'a' n times.
            for (int i = 0; i < n; i++) {
                sb.append('a');
            }
        } else {
            // If n is even, use 'a' n-1 times and 'b' once.
            // n-1 is odd, and 1 is odd.
            for (int i = 0; i < n - 1; i++) {
                sb.append('a');
            }
            sb.append('b');
        }
        return sb.toString();
    }
}
```

**Alternative Implementation using `char[]` (often slightly faster):**
```java
import java.util.Arrays;

class Solution {
    public String generateTheString(int n) {
        char[] chars = new char[n];
        Arrays.fill(chars, 'a');
        if (n % 2 == 0) {
            // If n is even, change the last character to 'b'.
            chars[n - 1] = 'b';
        }
        return new String(chars);
    }
}
```
### Algorithm
- Check if `n` is even or odd using the modulo operator (`n % 2`).
- **If `n` is odd**:
    - Create a string consisting of the character 'a' repeated `n` times.
- **If `n` is even**:
    - Create a string consisting of the character 'a' repeated `n-1` times.
    - Append the character 'b' to this string.
- Return the generated string.

# Solutions
### Java

```java
class Solution {
public
  String generateTheString(int n) {
    return (n % 2 == 1) ? "a".repeat(n) : "a".repeat(n - 1) + "b";
  }
}

```

### CPP

```cpp
class Solution {
public:
  string generateTheString(int n) {
    string ans(n, 'a');
    if (n % 2 == 0) {
      ans[0] = 'b';
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def generateTheString(self, n: int) -> str: return 'a' * \
        n if n & 1 else 'a' * (n - 1) + 'b'

```