Generate a String With Characters That Have Odd Counts: Parity Trick

LeetCode 1374, Generate a String With Characters That Have Odd Counts, gives you a single integer n. Your job is to return any string of length n where every character in the string appears an odd number of times.

For example:

• n = 4 could return "aaab" (a appears 3 times, b appears 1 time, both odd)
• n = 2 could return "ab" (a appears 1 time, b appears 1 time, both odd)
• n = 7 could return "aaaaaaa" (a appears 7 times, odd)

Why this problem matters

This is one of those problems that looks like it needs clever string manipulation, but once you see the parity trick, the solution is almost trivial. The real skill being tested is your ability to reduce a problem down to its simplest observation. That kind of thinking transfers directly to harder interview problems where the key insight is often a small mathematical observation hiding behind a wall of text.

The key insight: odd vs. even parity

The constraint says every character must appear an odd number of times. Here is the core observation:

• If n is odd, just repeat a single character n times. That character appears n times, which is odd. Done.
• If n is even, you cannot use a single character because that would give an even count. Instead, use (n - 1) copies of one character and 1 copy of another. Both n - 1 (which is odd, since n is even) and 1 are odd counts. Done.

That is the entire algorithm. No loops, no frequency maps, no backtracking. Just check whether n is odd or even and construct the string accordingly.

The code

def generateTheString(n: int) -> str:
    if n % 2 == 1:
        return "a" * n
    return "a" * (n - 1) + "b"

Walk through what happens:

1. Check if n is odd using n % 2 == 1.
2. If odd, return a string of n copies of "a". The only character present has an odd count.
3. If even, return (n - 1) copies of "a" followed by one "b". Both n - 1 and 1 are odd.

Visual walkthrough

Here is the algorithm running on n = 4 (even) and n = 7 (odd).

For n = 4, we get "aaab" with counts {a: 3, b: 1}. For n = 7, we get "aaaaaaa" with count {a: 7}. Every character count is odd in both cases.

Complexity analysis

There is no way to beat O(n) here since the output itself has length n. The solution is optimal.

Building blocks

This problem is built on two micro-patterns that show up frequently in string and math problems.

Parity checking

Checking whether a number is odd or even with the modulo operator is one of the most fundamental operations in algorithm design. You will use n % 2 in problems involving alternating patterns, pair counting, bit manipulation, and anywhere the even/odd distinction matters. Problems like Single Number rely on parity at a deeper level through XOR.

String construction by repetition

Building a string by repeating a character is a common primitive in constructive problems. Python's "a" * k creates a string of k copies efficiently. You will see this pattern in problems that ask you to construct a result satisfying certain frequency constraints, like building palindromes or generating specific character distributions.

Edge cases

n = 1. The smallest valid input. Since 1 is odd, return "a". One character with count 1 (odd).

n = 2. The smallest even input. Return "ab". Both characters appear once (odd).

Large n. The logic does not change. For n = 500, return 499 copies of "a" plus one "b". Both 499 and 1 are odd.

From understanding to recall

This problem is easy to understand right now. The parity trick is simple. But will you remember it in two weeks when you encounter a constructive string problem in an interview? Will the idea of splitting an even-length requirement into two odd parts come to you instantly?

Spaced repetition makes that happen. Instead of re-reading the full solution, you drill the building blocks (parity check, constructive output) at increasing intervals. After a few review cycles spread over days, the pattern becomes automatic. When you see a problem that asks you to construct something satisfying a parity constraint, the pieces are already there.

Related posts

• Single Number - Uses parity (via XOR) to isolate a unique element
• Happy Number - Another easy problem where a simple mathematical observation replaces brute force
• Length of Last Word - A simple string problem where the trick is choosing the right direction to scan