LeetCode 1374 - Generate a String With Characters That Have Odd Counts

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to generate a string of length n such that each character in the string occurs an odd number of times. The string must consist only of lowercase English letters. The input n is a positive integer ranging from 1 to 500, so the algorithm needs to handle small and moderately large strings efficiently. The output can be any valid string that satisfies the odd-count condition; it does not need to match a specific pattern.

Effectively, we need to distribute characters so that each appears an odd number of times. A key observation is that an odd-length string can be filled entirely with one repeated character, while an even-length string requires at least two distinct characters so that each appears an odd number of times. The problem guarantees that n is at least 1, so there is always at least one valid solution.

Important edge cases include the smallest input n = 1 and even numbers like n = 2, where a naive solution that repeats a single character would fail because a character repeated an even number of times does not meet the requirement.

Approaches

A brute-force approach would try generating all possible strings of length n and checking the count of each character, which is infeasible for large n because the number of combinations grows exponentially.

The optimal approach leverages the key insight: only the parity of counts matters, not the specific characters. If n is odd, we can fill the string with a single character repeated n times. If n is even, we can repeat one character n - 1 times and use a different character once. This guarantees that all character counts are odd and the string length matches n.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26^n)	O(n)	Generate all strings, count occurrences, check odd condition
Optimal	O(n)	O(n)	Construct string directly using 1 or 2 characters based on parity

Algorithm Walkthrough

Check if n is odd.
If n is odd, choose any character, for example 'a', and repeat it n times. This automatically satisfies the odd-count condition because n is odd.
If n is even, choose two characters, for example 'a' and 'b'. Repeat 'a' n - 1 times and 'b' once. This ensures 'a' appears an odd number of times (n - 1, which is odd because n is even) and 'b' appears once (odd), satisfying the requirement.
Return the resulting string.

Why it works: By carefully choosing the count of each character based on whether n is odd or even, we guarantee that every character has an odd frequency. This construction always produces a valid string without the need for additional checks.

Python Solution

class Solution:
    def generateTheString(self, n: int) -> str:
        if n % 2 == 1:
            return 'a' * n
        else:
            return 'a' * (n - 1) + 'b'

In the Python implementation, we use a simple conditional check to determine if n is odd or even. For odd n, we repeat 'a' n times. For even n, we repeat 'a' n - 1 times and append 'b'. This guarantees that all characters have odd counts and the string length is exactly n.

Go Solution

func generateTheString(n int) string {
    if n % 2 == 1 {
        return strings.Repeat("a", n)
    } else {
        return strings.Repeat("a", n-1) + "b"
    }
}

In Go, we use the strings.Repeat function to repeat a character multiple times. The logic mirrors the Python solution: if n is odd, repeat "a" n times; if even, repeat "a" n-1 times and append "b". No special handling of memory or slices is needed because Go efficiently handles string concatenation in this context.

Worked Examples

Example 1: n = 4

n is even. We repeat 'a' 4 - 1 = 3 times and append 'b' once.

String: "aaab"

Counts: 'a': 3, 'b': 1 - both odd

Example 2: n = 2

n is even. We repeat 'a' 1 time and append 'b'.

String: "ab"

Counts: 'a': 1, 'b': 1 - both odd

Example 3: n = 7

n is odd. We repeat 'a' 7 times.

String: "aaaaaaa"

Counts: 'a': 7 - odd

Step	n	Action	Resulting String	Counts
1	4	Even	'a' * 3 + 'b'	'a':3, 'b':1
2	2	Even	'a' * 1 + 'b'	'a':1, 'b':1
3	7	Odd	'a' * 7	'a':7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We construct a string of length `n` by repeating characters, which takes O(n) time.
Space	O(n)	The output string itself requires O(n) space. No additional data structures are used.

The algorithm is efficient because it directly constructs the string without any unnecessary iteration or counting.

Test Cases

solution = Solution()

# Provided examples
assert solution.generateTheString(4) in ["aaab", "bbba"]  # Even length
assert solution.generateTheString(2) in ["ab", "ba"]      # Small even
assert solution.generateTheString(7) == "aaaaaaa"          # Odd length

# Edge cases
assert solution.generateTheString(1) == "a"               # Smallest n
assert solution.generateTheString(500)  # Large even, should succeed
assert solution.generateTheString(499) == "a" * 499       # Large odd

Test	Why
n=4	Even length, must use two characters
n=2	Smallest even, minimal two characters
n=7	Odd length, single character repeated
n=1	Smallest possible n
n=500	Large even number, tests performance
n=499	Large odd number, single repeated character

Edge Cases

n = 1: This is the smallest possible input. Only one character is needed, which is automatically odd. The implementation correctly handles this by returning 'a'.

Even n = 2: The smallest even input requires at least two characters to satisfy the odd-count condition. The code appends a second character 'b' to ensure both counts are odd.

Large n near 500: Testing both large odd and even values ensures the solution scales. For odd n, a single character is repeated; for even n, one character is repeated n-1 times and another character is appended. This prevents performance issues and guarantees correctness.