Given a string S containing N lowercase English alphabets and a dictionary Dict that maps all lowercase English alphabets from āaā to āzā to either 1 or -1. For a string of length K, the following operation can be applied:
- Find the maximum character from index 1 to K, and find the dictionary mapping of the respective maximum character.
- If dictionary mapping is 1, increment all characters from 1 to K, i.e. āaā becomes ābā, ābā becomes ācā, . . . , āzā becomes āaā.
- If dictionary mapping is -1, decrement all characters from 1 to K. i.e. āaā becomes āzā, ābā becomes āaā, . . . , āzā becomes āyā
Ā Perform the described operation for each prefix of the string of length 1 to N.
The task is to determine the count of each lowercase English alphabet after performing the described operation for each prefix of the string of length 1 to N.
Examples:
Input: S=āabā, Dict[] = [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]
Output: 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Ā
Explanation:
For Prefix of length 1: Max character = āaā, Mapping = 1. So, increment prefix string. S=ābbā.
For Prefix of length 2: Max character = ābā, Mapping = -1. So, decrement prefix string. S = āaaā.Input: S=āabcbā, Dict[] = [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]
Output: 0 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Ā
Explanation:
For Prefix of length 1: Max character = āaā, Mapping = 1. So, increment prefix string. S=ābbcbā.
For Prefix of length 2: Max character = ābā, Mapping = -1. So, decrement prefix string. S = āaacbā.
For Prefix of length 3: Max character = ācā, Mapping = 1. So, increment prefix string. S=ābbdbā.
For Prefix of length 4: Max character = ādā, Mapping = 1. So, increment prefix string. S = āccecā.
Ā
Approach: The solution is based on greedy approach. Follow the below steps to solve this problem:
- Run a loop from i = 0 to i < N and in that loop run another loop from j = i to j >= 0 (to traverse the prefix).
- Now find the maximum element in that prefix and the number that it has been mapped to in Dict, say mp.
- Then apply the increment or decrement operation according to the number mp.
- Now, create a vector ans, to store the frequency of each element.
- Traverse the whole string and fill vector ans.
- Print the elements of vector ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Ā
// Function to find the frequency of// all character after performing N operationsvoid processString(string& S, vector<int>& Dict){Ā Ā Ā Ā int N = S.length();Ā Ā Ā Ā char mx;Ā
Ā Ā Ā Ā // Vector to store the frequency Ā Ā Ā Ā // of all charactersĀ Ā Ā Ā vector<int> ans(26, 0);Ā Ā Ā Ā for (int i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā Ā Ā mx = 96;Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 0; j <= i; j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā mx = max(mx, S[j]);Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 0; j <= i; j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'a' and Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is -1 then Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // make S[j] equals to 'z'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (S[j] + Dict[mx - 'a'] < 97) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = S[j] + Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Dict[mx - 'a'] + 26;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'z' and Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is 1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // then make S[j] equals to 'a'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā else if (S[j] + Dict[mx - 'a'] Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā > 122) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = S[j] + Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Dict[mx - 'a'] - 26;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] += Dict[mx - 'a'];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā for (int i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā Ā Ā ans[S[i] - 'a']++;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā for (auto x : ans) {Ā Ā Ā Ā Ā Ā Ā Ā cout << x << ' ';Ā Ā Ā Ā }}Ā
// Driver codeint main(){Ā
Ā Ā Ā Ā string S = "ab";Ā Ā Ā Ā vector<int> DictĀ Ā Ā Ā Ā Ā Ā Ā = { 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 };Ā Ā Ā Ā processString(S, Dict);Ā Ā Ā Ā Ā Ā Ā Ā Ā return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{Ā
Ā Ā // Function to find the frequency ofĀ Ā // all character after performing N operationsĀ Ā static void processString(char[] S, int[] Dict)Ā Ā {Ā Ā Ā Ā int N = S.length;Ā Ā Ā Ā char mx;Ā
Ā Ā Ā Ā // Vector to store the frequency Ā Ā Ā Ā // of all charactersĀ Ā Ā Ā int[] ans = new int[26];Ā Ā Ā Ā for (int i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā mx = 96;Ā Ā Ā Ā Ā Ā for (int j = 0; j <= i; j++) {Ā Ā Ā Ā Ā Ā Ā Ā mx = (char) Math.max(mx, S[j]);Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā for (int j = 0; j <= i; j++) Ā Ā Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'a' and Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is -1 then Ā Ā Ā Ā Ā Ā Ā Ā // make S[j] equals to 'z'Ā Ā Ā Ā Ā Ā Ā Ā if (S[j] + Dict[mx - 'a'] < 97) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = (char) (S[j] + Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Dict[mx - 'a'] + 26);Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'z' and Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is 1Ā Ā Ā Ā Ā Ā Ā Ā // then make S[j] equals to 'a'Ā Ā Ā Ā Ā Ā Ā Ā else if (S[j] + Dict[mx - 'a'] Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā > 122) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = (char) (S[j] + Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Dict[mx - 'a'] - 26);Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] += Dict[mx - 'a'];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā for (int i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā ans[S[i] - 'a']++;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā for (int x : ans) {Ā Ā Ā Ā Ā Ā System.out.print(x +" ");Ā Ā Ā Ā }Ā Ā }Ā
Ā Ā // Driver codeĀ Ā public static void main(String[] args)Ā Ā {Ā
Ā Ā Ā Ā char []S = "ab".toCharArray();Ā Ā Ā Ā int[] DictĀ Ā Ā Ā Ā Ā = { 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 };Ā Ā Ā Ā processString(S, Dict);Ā Ā }}Ā
// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approachĀ
# Function to find the frequency of# all character after performing N operationsdef processString(S, Dict):Ā Ā Ā Ā N = len(S);Ā Ā Ā Ā mx = '';Ā
Ā Ā Ā Ā # Vector to store the frequencyĀ Ā Ā Ā # of all charactersĀ Ā Ā Ā ans = [0 for i in range(26)];Ā Ā Ā Ā for i in range(N):Ā Ā Ā Ā Ā Ā Ā Ā mx = chr(96);Ā Ā Ā Ā Ā Ā Ā Ā for j in range(i+1):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā mx = chr(max(ord(mx), ord(S[j])));Ā
Ā Ā Ā Ā Ā Ā Ā Ā for j in range(i + 1):Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # If S[j] is ord('a') andĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Dict[S[j]] is -1 thenĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # make S[j] equals to 'z'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (ord(S[j]) + Dict[ord(mx) - ord('a')] < 97):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = ord(S[j] + Dict[ord(mx) - ord('a')] + 26);Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # If S[j] is 'z' andĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Dict[S[j]] is 1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # then make S[j] equals to ord('a')Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elif (ord(S[j]) + Dict[ord(mx) - ord('a')] > 122):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = ord(ord(S[j]) + Dict[ord(mx) - ord('a')] - 26);Ā
Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā else:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā tempc = chr(ord(S[j]) + Dict[ord(mx) - ord('a')]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S= S[0:j]+tempc+S[j:]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā #S[j] = tempc;Ā
Ā Ā Ā Ā for i in range(N):Ā Ā Ā Ā Ā Ā Ā Ā ans[ord(S[i]) - ord('a')] += 1;Ā
Ā Ā Ā Ā for x in ans:Ā Ā Ā Ā Ā Ā Ā Ā print(x, end=" ");Ā
# Driver codeif __name__ == '__main__':Ā Ā Ā Ā S = "ab";Ā Ā Ā Ā Dict = [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];Ā Ā Ā Ā processString(S, Dict);Ā Ā Ā Ā Ā Ā Ā Ā Ā # This code is contributed by 29AjayKumar |
C#
// C# program for the above approachusing System;Ā
public class GFG{Ā
Ā Ā // Function to find the frequency ofĀ Ā // all character after performing N operationsĀ Ā static void processString(char[] S, int[] Dict)Ā Ā {Ā Ā Ā Ā int N = S.Length;Ā Ā Ā Ā char mx;Ā
Ā Ā Ā Ā // List to store the frequency Ā Ā Ā Ā // of all charactersĀ Ā Ā Ā int[] ans = new int[26];Ā Ā Ā Ā for (int i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā mx = (char)96;Ā Ā Ā Ā Ā Ā for (int j = 0; j <= i; j++) {Ā Ā Ā Ā Ā Ā Ā Ā mx = (char) Math.Max(mx, S[j]);Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā for (int j = 0; j <= i; j++) Ā Ā Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'a' and Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is -1 then Ā Ā Ā Ā Ā Ā Ā Ā // make S[j] equals to 'z'Ā Ā Ā Ā Ā Ā Ā Ā if (S[j] + Dict[mx - 'a'] < 97) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = (char) (S[j] + Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Dict[mx - 'a'] + 26);Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'z' and Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is 1Ā Ā Ā Ā Ā Ā Ā Ā // then make S[j] equals to 'a'Ā Ā Ā Ā Ā Ā Ā Ā else if (S[j] + Dict[mx - 'a'] Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā > 122) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = (char) (S[j] + Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Dict[mx - 'a'] - 26);Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] += (char)Dict[mx - 'a'];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā for (int i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā ans[S[i] - 'a']++;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā foreach (int x in ans) {Ā Ā Ā Ā Ā Ā Console.Write(x +" ");Ā Ā Ā Ā }Ā Ā }Ā
Ā Ā // Driver codeĀ Ā public static void Main(String[] args)Ā Ā {Ā
Ā Ā Ā Ā char []S = "ab".ToCharArray();Ā Ā Ā Ā int[] DictĀ Ā Ā Ā Ā Ā = { 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 };Ā Ā Ā Ā processString(S, Dict);Ā Ā }}Ā
// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approachĀ
let m = {Ā Ā Ā Ā 'a': 0,Ā Ā Ā Ā 'b': 1}Ā
// Function to find the frequency of// all character after performing N operationsfunction processString(S, Dict){Ā Ā Ā Ā let N = S.length;Ā Ā Ā Ā let mx = '';Ā
Ā Ā Ā Ā // Vector to store the frequency Ā Ā Ā Ā // of all charactersĀ Ā Ā Ā let ans = new Array(26).fill(0);Ā Ā Ā Ā for (let i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā Ā Ā mx = 96;Ā Ā Ā Ā Ā Ā Ā Ā for (let j = 0; j <= i; j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā mx = Math.max(mx, S[j].charCodeAt(0));Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā for (let j = 0; j <= i; j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'a' and Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is -1 then Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // make S[j] equals to 'z'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (S[j].charCodeAt(0) + Dict[m[mx]] < 97) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = String.fromCharCode(S[j].charCodeAt(0) + Dict[m[mx]] + 26);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If S[j] is 'z' and Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Dict[S[j]] is 1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // then make S[j] equals to 'a'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā else if (S[j].charCodeAt(0) + Dict[m[mx]] > 122) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = String.fromCharCode(S[j].charCodeAt(0) + Dict[m[mx]] - 26);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā S[j] = String.fromCharCode(S[j].charCodeAt(0) + Dict[m[mx]]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā for (let i = 0; i < N; i++) {Ā Ā Ā Ā Ā Ā Ā Ā ans[S[i].charCodeAt(0)]++;Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā ans.forEach(function(ele){Ā Ā Ā Ā Ā Ā Ā Ā document.write(ele + " ");Ā Ā Ā Ā })Ā
}Ā
// Driver codelet S = ['a', 'b'];let Dict = [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];processString(S, Dict);Ā
// The code is contributed by Gautam goel. </script> |
Output
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? Itās time for a change! Join our DSA course, where weāll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
