Append and Delete

Solutions The challenging part of this exercise is how to handle operations in excess. If a string is empty, we can consume as many operations we want (as the problem specifies). So, the easy case is when we have a number of operations that is greater than the sum of length of both strings. In this case the solution is “Yes” because we can just remove all the characters from one, consume excess operations by repeatedly performing the second operation from the empty string, and finally appending the other characters. [Read More]
string  math 

Beautiful Binary String

Solutions The problem can be solved with a greedy algorithm: replace all 010 with 011. Anytime a replace is performed, a counter is incremented: 1 2 3 4 5 6 7 8 n = input() B = list(input()) cnt = 0 for i in range(n): if B[i: i + 3] == ['0', '1', '0']: B[i + 2] = '1' cnt += 1 print(cnt) The code above works in-place but it does modify the input string. [Read More]

Bigger is Greater

Solutions This problem requires to find the smallest permutation of the input string that is also bigger than the input string. This is a classical problem in Computer Science (in mathematics, in general) and often it’s referred as finding the “next permutation in lexicographic ordering”. The method consists in: find the largest index \( i \) such that \( a[i] < a[i + 1] \). If no such index exists, the permutation is the last permutation; find the largest index \( j \) greater than \( i \) such that a[i] < a[j]; swap the value of \( a[i] \) with that of \( a[j] \); reverse the sequence from \( a[i + 1] \) up to and including the final element of the sequence. [Read More]
sort  string 

Making Anagrams

Solutions Two strings are anagrams of one another if they share the same characters and each character has the same frequency in both strings. Thus, we can easily solve this problem with a frequency table. Basically, we can add 1 for each character in a and subtract 1 for each character in b. Those characters with non-zero frequency must be deleted and then added to the total count. Here is an implementation in C++: [Read More]

Repeated String

Solutions Let’s call l the length of the string. Thus, we have copies = n / l copies of the string. Let’s call occ the number of occurrences of a in the string. Thus, we have at least occ * l occurrences of a. The extra number of a is calculated from the possible remainder of the first n / l characters in the string. So we calculate the number of a in the first n%l characters. [Read More]