Here, we will discuss the solution to Subbookkeeper from AIO 2024.
The score of a word is the number of times that two adjacent letters are the same. You will be given a word with exactly one missing letter (a ?). What is the largest score you can achieve by strategically choosing the replacement for the missing letter?
The best choice is to make the missing letter be equal to the second letter in the word. For example, if the input was ?ELLO, then the best word you can make is EELLO.
After choosing the replacement letter, we can calculate the score using a for loop and an if statement.
Consider an example: T?E. There are two reasonable choices: replace the ? with T or replace it with E. Both of these choices will result in the same score. More generally, the score will be the same no matter whether we replace the ? with the letter before or after it.
After solving subtasks 1 and 2, the last case is when the ? is the final letter in the word. In this case, we should replace it with the letter before. For example, AGRE? becomes AGREE. Combining our ideas, we get the following solution:
This solution has a time complexity of O(N) which is fast enough to score 100.
There is a second way to solve this problem. If we delete the ? and calculate the score, the answer will always be this value plus 1. For example, RE?EL becomes REEL with a score of 1. Adding 1 to this gives 2, which is the correct answer. Play around with some more examples and try to convince yourself about why this solution is correct!
This solution also has a time complexity of O(N). Both solutions are equally good, and will both score 100.
Below you can see full solution 1 written in Python and C++. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck.
# Open the input and output files.
input_file = open("bookin.txt", "r")
output_file = open("bookout.txt", "w")
# Read the value of N and the word from the input file.
N = int(input_file.readline().strip())
word = input_file.readline().strip()
for i in range(N):
if word[i] == '?':
if i < N-1:
# The ? is not the last letter
# The next line replaces ? with the letter after it, and stores this result in a variable called new_word
new_word = word[:i] + word[i+1] + word[i+1:]
# Below is an explanation of how it works
# word[:i] is all the letters before letter i
# word[i+1] is the next letter in the word
# word[i+1:] is all the letters after letter i
# So, if word = "SUBBOO?KEEPER", then:
# - word[:i] = "SUBBOO"
# - word[i+1] = "K"
# - word[i+1:] = "KEEPER"
else:
# The ? is the last letter
# The next line replaces ? with the letter before it, and stores this result in a variable called new_word
new_word = word[:i] + word[i-1]
# We now calculate the score of new_word
answer = 0
for i in range(N-1):
if new_word[i] == new_word[i+1]:
answer += 1
# Write the answer to the output file.
output_file.write("%d\n" % (answer))
# Finally, close the input/output files.
input_file.close()
output_file.close()#include <cstdio>
int N;
char word[200005];
int main(void) {
/* Open the input and output files. */
FILE *input_file = fopen("bookin.txt", "r");
FILE *output_file = fopen("bookout.txt", "w");
/* Read the value of N and the word from the input file. */
fscanf(input_file, "%d", &N);
fscanf(input_file, "%s", word);
for (int i = 0; i < N; i++) {
if (word[i] == '?') {
if (i < N-1) {
// The ? is not the last letter
word[i] = word[i+1];
} else {
// The ? is the last letter
word[i] = word[i-1];
}
}
}
// We now calculate the score of word
int answer = 0;
for (int i = 0; i < N-1; i++) {
if (word[i] == word[i+1]) {
answer++;
}
}
/* Write the answer to the output file. */
fprintf(output_file, "%d\n", answer);
/* Finally, close the input/output files. */
fclose(input_file);
fclose(output_file);
}