#strings

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]

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]

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]

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]

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]

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]

Solutions A solution consists in finding all the contiguous digits in the string, converting them to integers and putting them in a set for removing duplicates. Finally, outputting the size of the set: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int n; cin >> n; string input; while (n--) { cin >> input; set<int> integers; auto cur = begin(input); while (cur ! [Read More]

Solutions A simple solution that makes use of extra space consists in simply copying words backwards to a temporary array starting from the last one. However, an classical in-place solution exists and works in two steps: first reverse the string blindly and then reverse every single word individually. Note that the input of this puzzle contains multiple lines and empty ones must be preserved. Here is a C++ solution: 1 2 3 4 5 6 7 8 9 10 11 12 std::string s{std::istreambuf_iterator<char>(std::cin), {}}; // read full input into memory, preserving newlines and spaces std::reverse(begin(s), end(s)); // reverse the string blindly auto head = begin(s); while (head ! [Read More]

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]

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]