algoadvance

Leetcode 1374. Generate a String With Characters That Have Odd Counts Certainly! Let’s break this down into manageable sections.

Problem Statement

LeetCode Problem 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.

Clarifying Questions

  1. Input Constraints:
    • What is the range of n? Is n always a positive integer?
      • Assumption: n is a positive integer and typically falls within a reasonable range for standard string operations in Java.
  2. Character Choices:
    • Can we assume the string should consist of lowercase English letters?
      • Clarified: Yes, we can assume lowercase English letters.

Strategy

Given n, our goal is to return a string where each character appears an odd number of times. Let’s outline how we can achieve this:

  1. If n is odd, we can simply repeat the same character n times.
  2. If n is even, we can repeat one character n-1 times (which is odd) and another character 1 time (which is also odd). This way, the counts remain odd.

Both these approaches ensure that each character in the string appears an odd number of times.

Code

Here’s the implementation in Java:

public class Solution {
    public String generateTheString(int n) {
        StringBuilder result = new StringBuilder();
     
        if (n % 2 == 1) {
            // If n is odd, return a string with 'a' repeated n times
            for (int i = 0; i < n; i++) {
                result.append('a');
            }
        } else {
            // If n is even, return a string with 'a' repeated (n-1) times and 'b' repeated 1 time
            for (int i = 0; i < n - 1; i++) {
                result.append('a');
            }
            result.append('b'); // Adding one more character to make it even-sized
        }
        
        return result.toString();
    }
}

Time Complexity

The time complexity of this solution is O(n):

By following this approach, we ensure that the string generated meets the criteria of having each character appear an odd number of times.

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