Alternating Characters

Solutions This problem can be solved by counting the number of equal adjacent characters: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 size_t T; cin >> T; string s; while (T--) { cin >> s; auto cnt = 0; for (auto i=1; i<s.size(); ++i) { if (s[i]==s[i-1]) cnt++; } cout << cnt << "\n"; } This is an application of zip | map | reduce pattern: [Read More]

Anagram

Solutions Possible C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <set>#include <cstdio>#include <vector>#include <iostream>#include <algorithm>using namespace std; int main() { int T; cin >> T; string s; while (T--) { cin >> s; if (s.size() % 2) { cout << -1 << endl; continue; } multiset<char> inters; const auto splitIt = begin(s)+(s. [Read More]

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]

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]

Happy Ladybugs

Solutions This problem can be solved by considering a few things: if a ladybug’s color is unique in the set, the ladybug will never be happy (the solution is “NO”) if 1) does not occur and if there is at least one empty cell, then the solution is always “YES” since it’s always possible to rearrange the ladybugs in the best position if 2) does not occur then the solution is “YES” only if all the ladybugs are already happy (because they cannot be moved) The first two properties are easy to check by using a frequency table (can be implemented with a map/dictionary or with a statically-sized array, since the number of letters is known - \(|A-Z|\)|). [Read More]

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]

Palindrome Index

Solutions If the string is already a palindrome, -1 is the answer since no character need be removed. If the given string is not a palindrome, we must find one character that, once removed, will make it a palindrome. We can do this by checking if str[i] == str[N - 1 - i] where N is the length of the string for all i starting from i=0. Once this condition fails, all we have to do is to check if str[0:i-1] + str[i+1:N-1] is a palindrome. [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]

Super Reduced String

Solutions A solution changes the string by removing same adjacent elements. Here is a C++ implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <string>#include <iostream>#include <algorithm>using namespace std; int main() { string S; cin >> S; auto finder = [&]{ return adjacent_find(begin(S), end(S)); }; for (auto adjFind = finder(); adjFind != end(S); adjFind = finder()) { S. [Read More]