1374. Generate a String With Characters That Have Odd Counts

EasyString
Leetcode Link

Problem Description

The task in this problem is to construct a string that consists of exactly n characters where n is an integer input provided to the function. Importantly, each character within the resulting string must appear an odd number of times. For instance, if the string is composed of 3 ‘a’ characters and 1 ‘b’ character, both 'a' and 'b' occur an odd number of times, which is valid. The string can only be formed using lowercase English letters. There may be several valid strings that satisfy these conditions, and any one of them is considered an acceptable solution.

Intuition

To solve this problem, we first recognize a fundamental property of integers: every integer is either odd or even. We can leverage this property by building a string where all but potentially one character has an even count, and the remaining character (if necessary) has an odd count. This design ensures all characters collectively appear an odd number of times.

The solution's intuition is quite straightforward:

  • If n is odd, we can simply create a string consisting of n instances of the same character (e.g., 'a'). Since n is odd, our condition is immediately satisfied with just one character.
  • If n is even, we cannot use a single character an even number of times because it would not meet the odd occurrence requirement. In this case, we construct a string with n - 1 instances of one character (e.g., 'a') and 1 instance of another character (e.g., 'b'). The 'a's appear n - 1 times, which is odd since n is even, and the occurrence of 'b' is odd as well since it’s only there once.

By using this simple conditional operation, we guarantee our string meets the problem criteria regardless of whether n is odd or even.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following array represent a max heap?

Solution Approach

The implementation of the solution uses a simple conditional check to determine whether n is odd or even and then constructs the string accordingly.

Here's a breakdown of the solution algorithm:

  1. Use the bitwise AND operator & to check if n is odd or even. For any integer n, n & 1 will be 1 if n is odd and 0 if n is even.
    • n & 1 essentially checks the least significant bit of n. If it is 1, n is odd; if it is 0, n is even.
  2. If n is odd (n & 1 == 1), return a string of n 'a' characters.
    • This satisfies the condition since there is only one character, and it occurs n times, which is an odd number.
  3. If n is even (n & 1 == 0), return a string of n - 1 'a' characters concatenated with 'b'.
    • Here, 'a' occurs an odd number of times (n - 1), and 'b' occurs exactly once, which is also odd.

This approach does not require any complex data structures or algorithms. It simply uses two string concatenation operations and a bitwise operator for the conditional check. The time complexity is O(1) since the string construction involves a constant number of operations that do not depend on the size of n. The space complexity is also O(n), where n is the length of the result string, because we need to store the result string.

The code in context looks like this:

1class Solution:
2    def generateTheString(self, n: int) -> str:
3        # Check if n is odd using bitwise AND with 1
4        if n & 1:
5            # Return n 'a' chars if n is odd
6            return 'a' * n
7        else:
8            # Return n-1 'a' chars plus 'b' if n is even
9            return 'a' * (n - 1) + 'b'

Each part of the code correlates directly with the steps laid out in the algorithm above.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's go through the solution approach with a small example where n = 5 which is an odd number, and n = 6 which is an even number.

  • For n = 5:

    1. We check if n is odd or even. Here, 5 & 1 equals 1 indicating that n is odd.
    2. Since n is odd, we return a string that consists of 5 instances of the 'a' character. Therefore, the resulting string is 'aaaaa'.
    3. The string 'aaaaa' contains the character 'a' exactly 5 times, which is odd, satisfying the condition.

  • For n = 6:

    1. We check if n is odd or even. Here, 6 & 1 equals 0 indicating that n is even.
    2. Since n is even, we need to construct a string of 6 - 1 instances of 'a' and add 1 instance of 'b' at the end. Therefore, the resulting string is 'aaaaab'.
    3. In the string 'aaaaab', the character 'a' appears 5 times which is an odd number, and the character 'b' appears 1 time, which is also an odd number. This fulfills the requirement.

Using the methodology provided in the solution, we can quickly determine the correct form of the string for any given n by simply checking if it's odd or even and constructing the string accordingly. The simplicity of this approach ensures it is easy to understand and efficient to execute.

Solution Implementation

1class Solution:
2    def generate_the_string(self, n: int) -> str:
3        # If n is even, we generate a string with (n-1) 'a' characters and 1 'b' to make the length odd
4        # If n is odd, we generate a string with all 'a' characters, as odd-length palindrome is already non-equal
5        return 'a' * (n - 1) + 'b' if n % 2 == 0 else 'a' * n
6
1class Solution {
2    // Method to generate a string based on the input integer n
3    public String generateTheString(int n) {
4        StringBuilder stringBuilder = new StringBuilder(); // Initialize a StringBuilder to construct the string
5
6        if (n % 2 == 1) { // Check if n is odd
7            // If n is odd, append 'a' n times to the StringBuilder
8            for (int i = 0; i < n; i++) {
9                stringBuilder.append("a");
10            }
11        } else { // If n is even
12            // Append 'a' (n-1) times to make the length (n-1), ensuring the final string will have an odd count of 'a'
13            for (int i = 0; i < n - 1; i++) {
14                stringBuilder.append("a");
15            }
16            // Append 'b' once to make the total length of the string equal to n
17            stringBuilder.append("b");
18        }
19
20        // Convert StringBuilder to String and return the result
21        return stringBuilder.toString();
22    }
23}
24
1class Solution {
2public:
3    // This function generates a string with 'n' characters
4    // such that it has an odd count of at least one unique character
5    string generateTheString(int n) {
6        // Create a string 'result' with 'n' characters initialized to 'a'
7        string result(n, 'a');
8
9        // If 'n' is even, change the first character to 'b'
10        // to satisfy the condition of having odd count of unique characters
11        if (n % 2 == 0) {
12            result[0] = 'b';
13        }
14
15        // Return the resultant string
16        return result;
17    }
18};
19
1// Function to generate a string with a given length 'n' where each character is 'a'
2// but if 'n' is even, the first character will be 'b' to ensure that all characters 
3// are not the same.
4function generateTheString(n: number): string {
5    // Initialize an array of 'n' elements, all set to 'a'
6    const resultArray = Array(n).fill('a');
7
8    // If 'n' is even, set the first element to 'b' to meet the condition
9    if (n % 2 === 0) {
10        resultArray[0] = 'b';
11    }
12  
13    // Join the array into a string and return
14    return resultArray.join('');
15}
16
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

The time complexity of the function generateTheString is O(n) where n is the input to the function. This is because the function involves concatenating n or n-1 characters which takes linear time in the size of the number of characters to concatenate.

The space complexity of the function is also O(n) because it generates a string which requires space proportional to the number of characters in the string, which in this case is n or n-1.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫