Domain 1EasyCORE

Generate a String With Characters That Have Odd Counts

The problem requires generating a string of length `n` where each character in the string appears an odd number of times. The constraints are that the string must contain only lowercase English letters and that there can be multiple valid strings for a given `n`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1374. Generate a String With Characters That Have Odd Counts

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 76.9%


Problem Breakdown

The problem requires generating a string of length n where each character in the string appears an odd number of times. The constraints are that the string must contain only lowercase English letters and that there can be multiple valid strings for a given n.

Inputs:

  • An integer n (1 <= n <= 500)

Outputs:

  • A string of length n with each character appearing an odd number of times.

Implicit Constraints/Edge Cases:

  • If n is 1, the output should be a single character.
  • If n is even, we need to ensure that all characters have odd counts. This can be achieved by having one character appear n-1 times and another character appear once.
  • If n is odd, we can simply have one character repeated n times.

Intuition

A brute-force approach would involve generating all possible strings of length n and checking if each character appears an odd number of times. This approach is computationally expensive and infeasible given the constraints (1 <= n <= 500).

The key insight is to leverage the properties of odd numbers:

  • If n is odd, we can simply return a string with one character (e.g., ‘a’) repeated n times.
  • If n is even, we can return a string with one character (e.g., ‘a’) repeated n-1 times and another character (e.g., ‘b’) repeated once.

This approach ensures that each character appears an odd number of times while minimizing complexity.

Approach

  1. Check if n is odd or even:

    • If n is odd, return a string with one character (e.g., ‘a’) repeated n times.
    • If n is even, return a string with one character (e.g., ‘a’) repeated n-1 times and another character (e.g., ‘b’) repeated once.
  2. Return the constructed string:

Complexity Analysis

  • Time Complexity: O(n) because we are constructing a string of length n.
  • Space Complexity: O(n) for storing the resulting string.

Solution

def generateTheString(n):
    if n % 2 == 1:
        return 'a' * n
    else:
        return 'a' * (n - 1) + 'b'

Edge Cases Handled

  • Edge Case: n = 1

    • The output is “a”, which satisfies the condition of having one character with an odd count.
  • Edge Case: n = 2

    • The output can be “ab” or any other string where both characters have an odd count (e.g., “xy”).
  • Edge Case: n = 7

    • The output is “aaaaaaa”, which satisfies the condition of having one character with an odd count.

This solution efficiently handles all edge cases and adheres to the constraints provided.