search
HomeBackend DevelopmentC++Count of each lowercase character in each prefix of length 1 to N after performing the described operation

Count of each lowercase character in each prefix of length 1 to N after performing the described operation

In this problem, we need to perform the given operation for each string prefix. Finally, we need to count the frequency of each character.

We can use a greedy algorithm to solve this problem. We need to take each prefix of length K and update its characters according to the given conditions. We can use map to calculate the frequency of characters in the final string.

Problem Statement - We are given a string tr containing N lowercase alphabetic characters. Additionally, we are given a mapping list, containing a total of 26 elements. Each element is mapped to lowercase characters based on its value. For example, mapping[0] maps to "a", mapping[1] maps to "b", and mapping[25] maps to "z". Additionally, the mapped array contains 1 or -1.

We need to do the following.

  • Get the maximum characters from the prefix of length K and get the mapping value from the 'mapping' array.

  • If the mapped value is 1, increase all prefix elements by 1.

  • If the mapped value is -1, decrement all prefix elements by 1.

Here, adding elements means ‘a’ −> ‘b’, ‘b’ −> ‘c’,… ‘z’ −> ‘a’.

Decreasing elements mean, ‘a’->‘z’, ‘b’->‘a’,…. ‘z’->‘y’.

We need to perform the above operation for each prefix of length 1

ExampleExample

enter

mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = ‘progress’

Output

0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0

illustrate

  • In a prefix of length 1, the largest character is 'p', which maps to -1. Therefore, the updated string will be 'orogress'.

  • In a prefix of length 2, the maximum character is ‘r’ and the mapping is -1. Therefore, the updated string will be "nqogress".

  • In a prefix of length 3, the largest character is 'q', and the mapping value is 1. Therefore, the updated string is 'orpgress'.

  • When we are done with everything, the final string will be 'pqmfpdqr', which contains 1 'f', 2 'p', 2 'q', 1 'm', 1 'd' and 1 'd' 'r'. In the output, we print the frequency of each character in the resulting string.

enter

mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = "ab", 

Output

1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Explanation− After performing all operations, the final string is 'ac' and we printed the frequency of each character.

method one

In this method, we will iterate through the string and take the value of K equal to the index P. After that, we will take the prefix with length equal to P, find the largest character, take the mapped value, and update all prefix characters accordingly.

algorithm

Step 1 − Define the ‘max_char’ variable to store the maximum character for the given prefix.

Step 2 − Similarly, initialize a list of length 26 with zeros in order to store the frequency of each character in the final string.

Step 3- Start looping through the string and initialize the "max_char" variable with 96 inside the loop.

Step 4 - Use nested loops to find the largest character from a prefix of length p.

Step 5 - Update each character of the prefix by adding the mapped value of max_char.

Step 7 - If the updated character is smaller than "a", update it to "z".

Step 8 - If the updated character is larger than "z", update it to "a".

Step 9− Finally, store the frequency of each character in a list by looping through the updated string.

Step 10- Print the frequency of characters.

Example

#include <bits/stdc++.h>
using namespace std;

void performOperations(string &str, vector<int> &mapping) {
    int len = str.length();
    char max_char;
    //  array to store the final frequency of each character
    int freq[26] = {0};
    for (int p = 0; p < len; p++) {
        max_char = 96;
        // Get the maximum character from the prefix string
        for (int q = 0; q <= p; q++) {
            max_char = max(max_char, str[q]);
        }
        // Update the prefix string by adding the max character's value.
        for (int q = 0; q <= p; q++) {
            // adding the mapping value to the current character
            str[q] += mapping[max_char - 'a'];
            // If the updated value is greater than z or less than a, update it
            if (str[q] < 'a') {
                str[q] = 'z';
            } else if (str[q] > 'z') {
                str[q] = 'a';
            }
        }
    }
    // Counting frequency of each character
    for (int p = 0; p < len; p++) {
        freq[str[p] - 'a']++;
    }
    // print count of each character in the updated string
    for (auto ch : freq) {
        cout << ch << ' ';
    }
}
int main() {
    string S = "progress";
    vector<int> mapping = {-1, 1, 1, -1, 1, 1, -1, -1,
                           -1, 1, 1, 1, -1, 1, -1, 1, -1,
                           1, -1, 1, 1, 1, -1, 1, 1, 1};
    performOperations(S, mapping);
    return 0;
}

Output

0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0

Time complexity− O(N*N) because we use two nested loops to traverse the string.

Space complexity− O(1), because we use constant space to store the frequency of characters.

in conclusion

We perform the given operation on the input string and print the character frequency of the updated string in the output. Programmers can also use maps in C to store character frequencies instead of using lists. For more practice, the programmer could try printing the cumulative frequency of each character in the updated string.

The above is the detailed content of Count of each lowercase character in each prefix of length 1 to N after performing the described operation. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
C   Interview Questions and Answers: Ace Your Next Technical AssessmentC Interview Questions and Answers: Ace Your Next Technical AssessmentApr 28, 2025 am 12:10 AM

C In interviews, smart pointers are the key tools that help manage memory and reduce memory leaks. 1) std::unique_ptr provides exclusive ownership to ensure that resources are automatically released. 2) std::shared_ptr is used for shared ownership and is suitable for multi-reference scenarios. 3) std::weak_ptr can avoid circular references and ensure secure resource management.

The Future of C  : Adaptations and InnovationsThe Future of C : Adaptations and InnovationsApr 27, 2025 am 12:25 AM

The future of C will focus on parallel computing, security, modularization and AI/machine learning: 1) Parallel computing will be enhanced through features such as coroutines; 2) Security will be improved through stricter type checking and memory management mechanisms; 3) Modulation will simplify code organization and compilation; 4) AI and machine learning will prompt C to adapt to new needs, such as numerical computing and GPU programming support.

The Longevity of C  : Examining Its Current StatusThe Longevity of C : Examining Its Current StatusApr 26, 2025 am 12:02 AM

C is still important in modern programming because of its efficient, flexible and powerful nature. 1)C supports object-oriented programming, suitable for system programming, game development and embedded systems. 2) Polymorphism is the highlight of C, allowing the call to derived class methods through base class pointers or references to enhance the flexibility and scalability of the code.

C# vs. C   Performance: Benchmarking and ConsiderationsC# vs. C Performance: Benchmarking and ConsiderationsApr 25, 2025 am 12:25 AM

The performance differences between C# and C are mainly reflected in execution speed and resource management: 1) C usually performs better in numerical calculations and string operations because it is closer to hardware and has no additional overhead such as garbage collection; 2) C# is more concise in multi-threaded programming, but its performance is slightly inferior to C; 3) Which language to choose should be determined based on project requirements and team technology stack.

C  : Is It Dying or Simply Evolving?C : Is It Dying or Simply Evolving?Apr 24, 2025 am 12:13 AM

C isnotdying;it'sevolving.1)C remainsrelevantduetoitsversatilityandefficiencyinperformance-criticalapplications.2)Thelanguageiscontinuouslyupdated,withC 20introducingfeatureslikemodulesandcoroutinestoimproveusabilityandperformance.3)Despitechallen

C   in the Modern World: Applications and IndustriesC in the Modern World: Applications and IndustriesApr 23, 2025 am 12:10 AM

C is widely used and important in the modern world. 1) In game development, C is widely used for its high performance and polymorphism, such as UnrealEngine and Unity. 2) In financial trading systems, C's low latency and high throughput make it the first choice, suitable for high-frequency trading and real-time data analysis.

C   XML Libraries: Comparing and Contrasting OptionsC XML Libraries: Comparing and Contrasting OptionsApr 22, 2025 am 12:05 AM

There are four commonly used XML libraries in C: TinyXML-2, PugiXML, Xerces-C, and RapidXML. 1.TinyXML-2 is suitable for environments with limited resources, lightweight but limited functions. 2. PugiXML is fast and supports XPath query, suitable for complex XML structures. 3.Xerces-C is powerful, supports DOM and SAX resolution, and is suitable for complex processing. 4. RapidXML focuses on performance and parses extremely fast, but does not support XPath queries.

C   and XML: Exploring the Relationship and SupportC and XML: Exploring the Relationship and SupportApr 21, 2025 am 12:02 AM

C interacts with XML through third-party libraries (such as TinyXML, Pugixml, Xerces-C). 1) Use the library to parse XML files and convert them into C-processable data structures. 2) When generating XML, convert the C data structure to XML format. 3) In practical applications, XML is often used for configuration files and data exchange to improve development efficiency.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool