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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Generate a String With Characters That Have Odd Counts

Number: 1490

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer n, return a string with n characters such that each character in the string occurs an odd number of times. The string must consist only of lowercase English letters. If there are multiple valid answers, you can return any one of them.

Key Insights

  • If n is odd, a string made up of the same character repeated n times will have an odd count.
  • If n is even, using one character repeated (n - 1) times (which is odd) combined with a second character (occurring once, also odd) results in a valid string.
  • The problem can be solved in constant time per character with a simple string construction.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The algorithm checks whether n is odd or even. If n is odd, it returns a string consisting of a single repeated character (like 'a') n times. If n is even, it returns a string with (n-1) repetitions of one character (like 'a') and appends another different character (like 'b'). This guarantees that every character has an odd count: (n-1) is odd when n is even and 1 is odd.

Code Solutions

# Python solution with line-by-line explanation

def generateTheString(n):
    # If n is odd, return a string of 'a' repeated n times because n is odd.
    if n % 2 == 1:
        return "a" * n
    # If n is even, return (n-1) 'a's and one 'b' to ensure both counts are odd.
    return "a" * (n - 1) + "b"

# Example usage:
print(generateTheString(4))  # Expected output: "aaab" (or any valid string)
← Back to All Questions