Return to Answer

One approach to avoid string copying and improve the time complexity from \$\Theta(m^2)\$ to \$\Theta(m)\$ (\$m\$ is the output string length) for each output string is to store characters of strings in a list and modify it in-place.

from typing import List, Iterable

def lex_string_gen_recursive(cur_depth: int, ch_list: List[str], alphabet: Iterable[str]):
    yield "".join(ch_list)
    if cur_depth < len(ch_list):
        next_depth = cur_depth + 1
        for ch in alphabet:
            ch_list[cur_depth] = ch
            yield from lex_string_gen_recursive(next_depth, ch_list, alphabet)
        ch_list[cur_depth] = ""

def lex_string_gen(max_length: int, alphabet: Iterable[str]):
    yield from lex_string_gen_recursive(0, [""] * max_length, sorted(alphabet))

Test:

list(lex_string_gen(3, "ab"))

Output:

['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']

One approach to avoid string copying and improve the time complexity from \$\Theta(m^2)\$ to \$\Theta(m)\$ (\$m\$ is the output string length) for each output string is to store characters of strings in a list and modify it in-place.

from typing import List, Iterable

def lex_string_gen_recursive(cur_depth: int, ch_list: List[str], alphabet: Iterable[str]) -> Iterable[str]:
    yield "".join(ch_list)
    if cur_depth < len(ch_list):
        next_depth = cur_depth + 1
        for ch in alphabet:
            ch_list[cur_depth] = ch
            yield from lex_string_gen_recursive(next_depth, ch_list, alphabet)
        ch_list[cur_depth] = ""

def lex_string_gen(max_length: int, alphabet: Iterable[str]) -> Iterable[str]:
    yield from lex_string_gen_recursive(0, [""] * max_length, sorted(alphabet))

Test:

list(lex_string_gen(3, "ab"))

Output:

['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']

One approach to avoid string copying and improve the time complexity from \$\Theta(m^2)\$ to \$\Theta(m)\$ (\$m\$ is the output string length) for each output string is to store characters of strings in a list and modify it in-place.

from typing import List, Iterable

def lex_string_gen_recursive(cur_depth: int, ch_list: List[str], alphabet: Iterable[str]):
    yield "".join(ch_list)
    if cur_depth < len(ch_list):
        next_depth = cur_depth + 1
        for ch in alphabet:
            ch_list[cur_depth] = ch
            yield from lex_string_gen_recursive(next_depth, ch_list, alphabet)
        ch_list[cur_depth] = ""

def lex_string_gen(max_length: int, alphabet: Iterable[str]):
    yield from lex_string_gen_recursive(0, [""] * max_length, alphabet)

Test:

list(lex_string_gen(3, "ab"))

Output:

['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']

One approach to avoid string copying and improve the time complexity from \$\Theta(m^2)\$ to \$\Theta(m)\$ (\$m\$ is the output string length) for each output string is to store characters of strings in a list and modify it in-place.

from typing import List, Iterable

def lex_string_gen_recursive(cur_depth: int, ch_list: List[str], alphabet: Iterable[str]):
    yield "".join(ch_list)
    if cur_depth < len(ch_list):
        next_depth = cur_depth + 1
        for ch in alphabet:
            ch_list[cur_depth] = ch
            yield from lex_string_gen_recursive(next_depth, ch_list, alphabet)
        ch_list[cur_depth] = ""

def lex_string_gen(max_length: int, alphabet: Iterable[str]):
    yield from lex_string_gen_recursive(0, [""] * max_length, sorted(alphabet))

Test:

list(lex_string_gen(3, "ab"))

Output:

['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']

One approach to improve time complexity is to store characters of strings in a list and modify it in-place.

from typing import List, Iterable

def lex_string_gen_recursive(cur_depth: int, ch_list: List[str], alphabet: Iterable[str]):
    yield "".join(ch_list)
    if cur_depth < len(ch_list):
        next_depth = cur_depth + 1
        for ch in alphabet:
            ch_list[cur_depth] = ch
            yield from lex_string_gen_recursive(next_depth, ch_list, alphabet)
        ch_list[cur_depth] = ""

def lex_string_gen(max_length: int, alphabet: Iterable[str]):
    yield from lex_string_gen_recursive(0, [""] * max_length, alphabet)

Test:

list(lex_string_gen(3, "ab"))

Output:

['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']

One approach to avoid string copying and improve the time complexity from \$\Theta(m^2)\$ to \$\Theta(m)\$ (\$m\$ is the output string length) for each output string is to store characters of strings in a list and modify it in-place.

from typing import List, Iterable

def lex_string_gen_recursive(cur_depth: int, ch_list: List[str], alphabet: Iterable[str]):
    yield "".join(ch_list)
    if cur_depth < len(ch_list):
        next_depth = cur_depth + 1
        for ch in alphabet:
            ch_list[cur_depth] = ch
            yield from lex_string_gen_recursive(next_depth, ch_list, alphabet)
        ch_list[cur_depth] = ""

def lex_string_gen(max_length: int, alphabet: Iterable[str]):
    yield from lex_string_gen_recursive(0, [""] * max_length, alphabet)

Test:

list(lex_string_gen(3, "ab"))

Output:

['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']