Problem 1374

Abstract / Summary

Create a string from given characters so that each character appears an odd number of times.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1374.py

class Solution:
    def generateTheString(self, n: int) -> str:
        if n % 2 == 1:
            return "a" * n
        else:
            return "a" + "b" * (n - 1)
6 lines | 173 bytes | submitted January 2, 2024 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 79% (100k+ submissions).

Typical patterns to solve this problem:
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a single method generateTheString. The method receives an integer n and returns a string of length n that satisfies a specific parity condition on the count of each character. The logic is concise, relying on a single conditional branch to decide between two possible string constructions.

Core Logic

The method begins by evaluating the parity of the input n.

if n % 2 == 1:
    return "a" * n
else:
    return "a" + "b" * (n - 1)

When n is odd, the method returns a string composed entirely of the character 'a', repeated n times. When n is even, the method constructs a string that starts with a single 'a' followed by n-1 occurrences of 'b'. This guarantees that the resulting string always contains an odd number of at least one character, satisfying the problem’s requirement.

Handling of Edge Cases

The conditional check n % 2 == 1 naturally covers the smallest positive inputs. For n = 1, the odd branch produces "a" which is a valid length-1 string. For n = 2, the even branch yields "ab" ("a" plus one 'b'), meeting the length constraint while ensuring the count of 'a' is odd. The implementation also gracefully handles larger values of n without additional special-case code, because the parity test and string multiplication scale uniformly across all integer inputs.

Performance Considerations

The method leverages Python’s built-in string multiplication operator (*). This operator creates the final string in a single operation, avoiding explicit loops or repeated concatenations that could incur additional overhead. By constructing the entire output in one step for each branch, the implementation minimizes the number of intermediate objects and reduces memory churn. The single conditional test ensures that only one of the two possible construction paths is executed, keeping the control flow minimal.

Summary of Execution Flow

The execution proceeds as follows: receive n, compute n % 2, select the appropriate branch, generate the required string using multiplication, and return the result. The design is straightforward, with clear separation between the odd and even scenarios, and each path directly produces the final output without further processing.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a magical machine that makes long trains of blocks. You tell the machine how many blocks it needs to use in total, and that is what the letter n stands for. If you give the machine an odd number like three or five, it happily fills the whole train with the letter a. This is because every block is the same friendly letter. If you give the machine an even number like four or six, it decides to do something a little different. It places one single a block at the very front of the line, and then it fills up all the rest of the empty spots with the letter b. This makes sure that the total number of blocks stays exactly what you asked for while following a special secret rule about how many times each letter appears.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.26 | σ = 1.17

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
qiyuangong Python
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
qiyuangong Python
varunu28 Java
YuriSpiridonov Python
30 links | 19 authors | 9 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

5 solutions   January 2, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality