Generate a String With Characters That Have Odd Counts - Video Solutions

Problem Overview: You need to construct any string of length n such that every character in the string appears an odd number of times. The characters can be any lowercase letters. The only constraint is that the frequency of each character must be odd.

Approach 1: All Characters Same If Odd, Add One If Even (O(n) time, O(1) space)

The key observation is that a string containing the same character repeated n times automatically satisfies the requirement when n is odd. If n is even, that repetition would produce an even count, which violates the rule. To fix this, generate n-1 copies of one character (for example 'a') and append a different character like 'b'. Now the counts become n-1 and 1, both odd numbers. The algorithm simply checks whether n is even or odd and constructs the string accordingly using basic string operations.

Approach 2: Alternate Characters for Even n (O(n) time, O(1) space)

Another valid construction uses two characters when n is even. Fill most of the string with one character and ensure both characters end up with odd frequencies. For example, repeat 'a' for n-1 positions and place 'b' once. This approach highlights the same insight from a slightly different perspective: only the parity of counts matters. As long as each character appears an odd number of times, the exact arrangement of characters is irrelevant. Implementation still involves a single pass string build using simple string construction techniques.

Recommended for interviews: Approach 1 is what interviewers expect. It shows you recognized the parity trick immediately and avoided unnecessary complexity. Many candidates overthink this problem with frequency maps or multiple characters. Demonstrating the simple observation that n odd → repeat one character, n even → split into n-1 and 1 shows strong reasoning with basic string manipulation.