Lesson 2

String Manipulation and Frequency Analysis with Alice in C++

Introduction

Hello! Are you ready for an exciting voyage into the wonderful realm of strings and data structures? Today, we will assist Alice, an aspiring cryptographer, with an intriguing string manipulation task. She loves playing with strings and has come up with a unique string encoding scheme. I assure you, this will be an enlightening journey that will stretch your programming muscles. Let's get started!

Task Statement

Alice has devised a unique way of encoding words. She takes a word and replaces each character with the next character in the alphabetical order. In other words, given a string word, for each character, if it's not z, she replaces it with the character that comes next alphabetically. For the character z, she replaces it with a.

Another element of Alice's algorithm involves frequency analysis. After shifting the characters, she counts the frequency of each character in the new string. Then, she creates an association of each character with its frequency and ASCII value. Each character maps to a number, which is a product of the ASCII value of the character and its frequency. Our task is to construct a list containing these products, sorted in descending order.

Example

For the input string "banana", the output should be {294, 222, 99}.

The string "banana" will be shifted to "cbobob".

Calculating the product of frequency and ASCII value for each character:

  • The ASCII value for c is 99; it appears once in the string, so its product is 991=9999 \cdot 1 = 99.
  • The ASCII value for b is 98; it appears three times in the string, so its product is 983=29498 \cdot 3 = 294.
  • The ASCII value for o is 111; it appears twice in the string, so its product is 1112=222111 \cdot 2 = 222.

Collecting these products into a list gives {99, 294, 222}. Sorting this list in descending order results in {294, 222, 99}.

Solution Building: Step 1 - Mapping each character to the next alphabetical character

Our first step involves mapping each character of the input string to the next alphabetical character. For this, we define the next_string as an empty string, storing the shift operation result. We then iterate over each character of the input string. If a character is not z, we replace it with the next alphabetical character. If it is z, we replace it with a.

Here's the updated function in C++:

C++
1std::string character_frequency_encoding(std::string word) { 2 std::string next_string = ""; 3 for (char & letter : word) { 4 next_string += (letter == 'z' ? 'a' : letter + 1); 5 } 6 return next_string; 7}
Solution Building: Step 2 - Counting the frequency of characters in `next_string`

The next step is to track the frequency of each character in next_string. We start by initializing an empty std::map<char, int>, frequency_map. Then, we iterate over next_string. If the current character exists in frequency_map, we increment its frequency by 1. If it doesn't exist, we add it to frequency_map with a frequency of 1.

Incorporating this step into the function, our code now looks like this:

C++
1std::map<char, int> count_frequency(const std::string &next_string) { 2 std::map<char, int> frequency_map; 3 for (const char & letter : next_string) { 4 if (frequency_map.find(letter) != frequency_map.end()) { 5 frequency_map[letter]++; 6 } else { 7 frequency_map[letter] = 1; 8 } 9 } 10 return frequency_map; 11}
Solution Building: Step 3 - Building the product list

Next, we calculate the numerical representation for each unique character. We initialize an empty std::vector<int>, combined_values, to store these numbers. For each character in frequency_map, we calculate the product of its ASCII representation and its frequency in next_string and append this to combined_values.

Here's the updated function:

C++
1std::vector<int> build_product_list(const std::map<char, int> &frequency_map) { 2 std::vector<int> combined_values; 3 for (const auto & item : frequency_map) { 4 combined_values.push_back(static_cast<int>(item.first) * item.second); 5 } 6 return combined_values; 7}
Solution Building: Step 4 - Sorting the final values

The final step is to sort the list combined_values in descending order using std::sort.

Here's our complete function:

C++
1#include <algorithm> 2#include <vector> 3#include <map> 4#include <string> 5#include <iostream> 6 7std::vector<int> character_frequency_encoding(std::string word) { 8 // Step 1: Mapping each character to the next alphabetical character 9 std::string next_string = ""; 10 for (char & letter : word) { 11 next_string += (letter == 'z' ? 'a' : letter + 1); 12 } 13 14 // Step 2: Counting the frequency of characters in next_string 15 std::map<char, int> frequency_map; 16 for (const char & letter : next_string) { 17 if (frequency_map.find(letter) != frequency_map.end()) { 18 frequency_map[letter]++; 19 } else { 20 frequency_map[letter] = 1; 21 } 22 } 23 24 // Step 3: Building the product list 25 std::vector<int> combined_values; 26 for (const auto & item : frequency_map) { 27 combined_values.push_back(static_cast<int>(item.first) * item.second); 28 } 29 30 // Step 4: Sorting the final values in descending order 31 std::sort(combined_values.begin(), combined_values.end(), std::greater<int>()); 32 33 // Return the sorted list 34 return combined_values; 35} 36 37// Example 38int main() { 39 std::string word = "banana"; 40 std::vector<int> result = character_frequency_encoding(word); 41 for(int value : result) { 42 std::cout << value << " "; 43 } 44 return 0; 45}
Lesson Summary

Well done! You've successfully tackled an intricate problem that required you to exercise multiple topics such as string manipulation, map processing, and vector sorting. This task underscored the importance of reusing already calculated values. I encourage you to apply what you've learned today to other tasks. Many more exciting challenges are waiting for you in the upcoming practice sessions. Happy coding!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.