APCS Jun 2024 - o078 Q3 [Python]

Problem statement:

Given a set of K letters and a string S, find the lexicographically smallest string of length L formed from the set that is not a substring of S. For example, with {a, c, m}, the length-2 strings in increasing order are aa < ac < am < ca < cc < cm < ma < mc < mm. If S is accaamcm, the smallest missing string is ma.

def generate_strings(letters, length, current_string, all_strings):
    if length == 0:
        all_strings.append(current_string)
        return
    for letter in letters:
        generate_strings(letters, length - 1, current_string + letter, all_strings)

letters = list(input())
L = int(input())
S = input()

all_strings = []
generate_strings(letters, L, "", all_strings)

for string in all_strings:
    if string not in S:
        print(string)
        break

---

Solution report

1. Recursion

   def generate_strings(letters, length, current_string, all_strings):
   if length == 0:
       all_strings.append(current_string)
       return
   for letter in letters:
       generate_strings(letters, length - 1, current_string + letter, all_strings)
   

   This recursive function generates all strings of the specified length from the given letters. For letters = ['a', 'b'] and length = 2:

   1. Start with generate_strings(['a', 'b'], 2, "", all_strings). Since length is not 0, enter the loop. The first letter is 'a', so call generate_strings(['a', 'b'], 1, "a", all_strings).
   2. In that second call, length is still not 0. Choose 'a' again and call generate_strings(['a', 'b'], 0, "aa", all_strings).
   3. In the third call, length is 0. Add "aa" to all_strings and return to the previous level.
   4. Back in the second call, continue the loop with 'b': generate_strings(['a', 'b'], 0, "ab", all_strings).
   5. In the fourth call, add "ab" to all_strings because length is 0, then return.

   Repeating this process produces "aa", "ab", "ba", and "bb", added to all_strings in order.

Key concepts:

• Recursion

---

• [✔️] You may use the code directly if needed.
• [✔️] Please credit the source when sharing.
• [✔️] This article’s solution report was written with AI assistance. Please point out any errors.

---

It can actually be faster

def generate_strings(letters, length, current_string, existing_strings):
    if length == 0:
        if current_string not in existing_strings:
            print(current_string)
            return True
        return False
    for letter in letters:
        if generate_strings(letters, length - 1, current_string + letter, existing_strings):
            return True
    return False

letters = list(input())
L = int(input())
S = input()

# 使用Set來提升查找效率
existing_strings = set(S[i:i+L] for i in range(len(S) - L + 1))

generate_strings(letters, L, "", existing_strings)

• My explanation skills are limited, so you’ll have to work this one out yourself :).

This article was translated from Traditional Chinese by AI. Meaning or wording may differ; please refer to the Traditional Chinese original as the authoritative version.