Generate a String With Characters That Have Odd Counts

Generate a String With Characters That Have Odd Counts - Problem

String Easy

Given an integer n, return a string with n characters such that each character in the 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.

Input & Output

Example 1 — Odd Length

$ Input: n = 3

› Output: aaa

💡 Note: String has 3 characters, character 'a' appears 3 times (odd count). Any single character repeated 3 times works.

Example 2 — Even Length

$ Input: n = 4

› Output: aaab

💡 Note: String has 4 characters, 'a' appears 3 times (odd), 'b' appears 1 time (odd). Both characters have odd counts.

Example 3 — Minimum Case

$ Input: n = 1

› Output: a

💡 Note: Single character string, 'a' appears 1 time (odd count). This is the smallest valid case.

Constraints

1 ≤ n ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n specifying string length

Process

Apply pattern based on n's parity

Output

String with all characters having odd counts

Key Takeaway

🎯 Key Insight: Use n's parity to determine pattern - odd n uses one character, even n uses two characters with specific counts

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is understanding parity: if n is odd, repeat one character n times (odd count). If n is even, use (n-1) of one character and 1 of another (both odd counts). Best approach is direct pattern. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Different Combinations	O(n²)	O(1)	Generate various combinations and check if all characters have odd counts
Optimized - Direct Pattern	O(n)	O(1)	Directly apply the optimal pattern based on n's parity

Brute Force - Try Different Combinations — Algorithm Steps

Generate different character combinations
Count frequency of each character
Check if all frequencies are odd

Visualization

Tap to expand

Step-by-Step Walkthrough

Check n

Determine if n is odd or even

Apply Pattern

Use appropriate pattern based on n

Result

Return string with odd character counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(int n) {
    char* result = (char*)malloc((n + 1) * sizeof(char));
    // Pattern 1: all same character if n is odd
    if (n % 2 == 1) {
        for (int i = 0; i < n; i++) {
            result[i] = 'a';
        }
    }
    // Pattern 2: (n-1) of one char + 1 of another if n is even
    else {
        for (int i = 0; i < n - 1; i++) {
            result[i] = 'a';
        }
        result[n - 1] = 'b';
    }
    result[n] = '\0';
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    char* result = solution(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Generating combinations and counting frequencies for each attempt

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for counters

✓ Linear Space

25.8K Views

Medium Frequency

~10 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try Different Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler