algoadvance

Leetcode 1374. Generate a String With Characters That Have Odd Counts

Problem Statement

1374. Generate a String With Characters That Have Odd Counts

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.

Example 1:

• Input: n = 4
• Output: "pppz"
• Explanation: "pppz" is a valid string since the occurrences of 'p' is 3 and 'z' is 1, both of which are odd. 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 occurrences of 'x' and 'y' are 1, both of which are odd. Note that there are many other valid strings such as "qz" and "he".

Example 3:

• Input: n = 7
• Output: "holasss"

Constraints:

• 1 <= n <= 500

Clarifying Questions:

1. Q: Is there a specific set of characters we have to use for generating the string?
   • A: No, you can use any lowercase English letters.
2. Q: If there are multiple outputs possible, does it matter which one we return?
   • A: No, any valid string is acceptable.
3. Q: Can the same character be used more than once in the string?
   • A: Yes, as long as each character’s count is odd, you can use the same character multiple times.

Strategy

To solve this problem, the main idea is to ensure that each character in the resultant string has an odd count. To achieve this:

1. When n is odd:
   • Simply use one character repeated n times, since n is odd.
2. When n is even:
   • Use one character n-1 times and another different character 1 time. This way, both characters will have an odd count.

This approach ensures that we cover all cases with minimal effort and guarantees the resultant string’s characters meet the criteria for having odd counts.

Code

#include <string>

class Solution {
public:
    std::string generateTheString(int n) {
        // If n is odd, use 'a' n times
        if (n % 2 == 1) {
            return std::string(n, 'a');
        }
        // If n is even, use 'a' (n-1) times and 'b' 1 time
        else {
            return std::string(n - 1, 'a') + 'b';
        }
    }
};

Time Complexity

The time complexity of this solution is O(n) because we are constructing a string of length n using simple operations which involve initializing and appending characters to the string.

• String construction: Creating a string of length n directly involves writing n characters, resulting in O(n) time complexity.

This solution is efficient and straightforward as it directly addresses both cases (when n is odd and when n is even) with minimal logic branching.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?