We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Generate a String With Characters That Have Odd Counts

Difficulty: Easy

Problem Description

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 multiple valid strings, return any of them.

Key Insights

  • Each character must appear an odd number of times in the final string.
  • To achieve an odd count, we can use one character in odd counts (1, 3, 5, etc.) and fill the rest with characters that also meet this requirement.
  • The simplest way to construct such a string is to use the same character repeatedly as needed.

Space and Time Complexity

Time Complexity: O(n) - We need to generate a string of length n. Space Complexity: O(1) - We only use a fixed amount of space for character storage, independent of n.

Solution

To solve the problem, we can generate a string by repeating a character to ensure it appears an odd number of times. For example, if we choose the character 'a', we can repeat it (n - 1) times and add a different character (like 'b') once to make sure the total length is n. This guarantees that the counts of both characters are odd.

Code Solutions

def generateOddCountString(n):
    if n % 2 == 0:
        # If n is even, use one character n-1 times and one different character once
        return 'a' * (n - 1) + 'b'
    else:
        # If n is odd, use one character n times
        return 'a' * n

# Example usage:
print(generateOddCountString(4))  # Output: "aaab"
print(generateOddCountString(2))  # Output: "ab"
print(generateOddCountString(7))  # Output: "aaaaaaa"
← Back to All Questions