Difficulty: Easy | Acceptance: 78.50% | Paid: No Topics: String
Given an integer n, return a string of length n with all lowercase English letters such that each character appears an odd number of times.
The returned string can contain any of the lowercase English letters. If there are multiple valid strings, return any of them.
Examples
Input: n = 4
Output: "pppz"
Explanation: "pppz" is a valid string since the character 'p' appears three times and the character 'z' appears once. Note that there are many other valid strings such as "ohhh" and "abaa".
Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since 'x' and 'y' appear once. Note that there are many other valid strings such as "ag" and "ur".
Input: n = 7
Output: "holasss"
Constraints
1 <= n <= 500
Simple Construction
Intuition If n is odd, we can use a single character n times. If n is even, we use one character n-1 times and another character once.
Steps
- Check if n is odd or even
- If odd, return ‘a’ repeated n times
- If even, return ‘a’ repeated (n-1) times followed by ‘b’
python
class Solution:
def generateTheString(self, n: int) -> str:
if n % 2 == 1:
return 'a' * n
else:
return 'a' * (n - 1) + 'b'
Complexity
- Time: O(n)
- Space: O(n)
- Notes: Simple and efficient solution with minimal operations
String Multiplication
Intuition Use string multiplication/repeat operations to construct the result efficiently.
Steps
- If n is odd, return ‘a’ multiplied by n
- If n is even, return ‘a’ multiplied by (n-1) plus ‘b’
python
class Solution:
def generateTheString(self, n: int) -> str:
return 'a' * n if n % 2 else 'a' * (n - 1) + 'b'
Complexity
- Time: O(n)
- Space: O(n)
- Notes: More concise code using built-in string operations
Greedy Construction
Intuition Build the string by adding characters one at a time, ensuring odd counts for all characters.
Steps
- Start with an empty string
- Add ‘a’ n-1 times
- If n is odd, add one more ‘a’, otherwise add ‘b’
python
class Solution:
def generateTheString(self, n: int) -> str:
result = []
for i in range(n - 1):
result.append('a')
if n % 2 == 1:
result.append('a')
else:
result.append('b')
return ''.join(result)
Complexity
- Time: O(n)
- Space: O(n)
- Notes: More verbose but demonstrates the greedy approach clearly