Scale Engineer

Generate a String With Characters That Have Odd Counts

Easy
#1274Time: O(26^n). For each of the `n` positions in the string, we have 26 choices of characters. This leads to an exponential number of paths to explore, making it impractical for all but the smallest values of `n`.Space: O(n). The maximum depth of the recursion is `n`. Additionally, we need O(26) or O(1) space to store the character counts. Thus, the space complexity is dominated by the recursion stack.
Data structures
String

Prompt

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

 

Example 1:

Input: n = 4
Output: "pppz"
Explanation: "pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".

Example 2:

Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".

Example 3:

Input: n = 7
Output: "holasss"

 

Constraints:

  • 1 <= n <= 500

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves exploring all possible combinations of characters to form a string of length n. We use a recursive function to build the string character by character. At the end, once a string of length n is formed, we check if it satisfies the condition that all character counts are odd. While this approach is guaranteed to find a solution, it is highly inefficient due to the vast number of possibilities it explores.

Algorithm

  • Define a recursive function findValidString(index, charCounts) that tries to build a valid string.
  • index is the current position in the string to fill (from 0 to n-1).
  • charCounts is an array of size 26 to store frequencies.
  • Base Case: If index == n:
    • Check if all non-zero counts in charCounts are odd.
    • If true, construct the string from charCounts and return it.
    • If false, return a special value indicating no solution found from this path (e.g., null).
  • Recursive Step:
    • Iterate through characters c from 'a' to 'z'.
    • Increment count for c in charCounts.
    • Call findValidString(index + 1, charCounts).
    • If the call returns a valid string, return it immediately.
    • Decrement count for c (backtrack).
  • If the loop finishes without finding a solution, return null.
  • The initial call would be findValidString(0, new int[26]).

Walkthrough

This method attempts to find a solution by systematically trying all possibilities. It's a brute-force method that is too slow for the given constraints but illustrates a general-purpose problem-solving strategy.

We can define a recursive function that tries to place a character at each position from 0 to n-1. After placing n characters, it checks if the resulting string is valid. If not, it backtracks and tries a different character.

Because this approach is computationally infeasible (O(26^n)), a full implementation would time out on any platform. It serves as a theoretical baseline for a 'worst-case' algorithm.

Complexity

Time

O(26^n). For each of the `n` positions in the string, we have 26 choices of characters. This leads to an exponential number of paths to explore, making it impractical for all but the smallest values of `n`.

Space

O(n). The maximum depth of the recursion is `n`. Additionally, we need O(26) or O(1) space to store the character counts. Thus, the space complexity is dominated by the recursion stack.

Trade-offs

Pros

  • It is a generic problem-solving technique that can, in theory, find a solution for any similar constraint satisfaction problem.

Cons

  • Extremely inefficient with exponential time complexity.

  • Impractical for the given constraints (1 <= n <= 500).

  • Overly complex to implement for such a simple problem.

Solutions

class Solution {public  String generateTheString(int n) {    return (n % 2 == 1) ? "a".repeat(n) : "a".repeat(n - 1) + "b";  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem