Recuento de cada carácter en minúscula después de realizar las operaciones descritas para cada prefijo de longitud 1 a N

Dada una string S que contiene N alfabetos ingleses en minúsculas y un diccionario Dict que mapea todos los alfabetos ingleses en minúsculas desde ‘a’ hasta ‘z’ a 1 o -1 . Para una string de longitud K , se puede aplicar la siguiente operación:

1. Encuentre el carácter máximo del índice 1 a K y encuentre la asignación de diccionario del carácter máximo respectivo.
2. Si el mapeo del diccionario es 1 , incremente todos los caracteres de 1 a K , es decir, ‘a’ se convierte en ‘b’, ‘b’ se convierte en ‘c’, . . . , ‘z’ se convierte en ‘a’.
3. Si la asignación de diccionario es -1 , disminuya todos los caracteres de 1 a K. es decir, ‘a’ se convierte en ‘z’, ‘b’ se convierte en ‘a’, . . . , ‘z’ se convierte en ‘y’

 Realice la operación descrita para cada prefijo de la string de longitud 1 a N.

La tarea es determinar el conteo de cada alfabeto inglés en minúsculas después de realizar la operación descrita para cada prefijo de la string de longitud 1 a N.

Ejemplos:

Entrada: 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]
Salida: 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 
Explicación:
para el prefijo de longitud 1: carácter máximo = ‘a’, asignación = 1. Por lo tanto, incremente la string de prefijo. S=”bb”.
Para Prefijo de longitud 2: Carácter máximo = ‘b’, Asignación = -1. Entonces, disminuya la string de prefijo. S = “aá”.

Entrada: 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]
Salida: 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 
Explicación:
para el prefijo de longitud 1: carácter máximo = ‘a’, asignación = 1. Por lo tanto, incremente la string de prefijo. S=”bbcb”.
Para Prefijo de longitud 2: Carácter máximo = ‘b’, Asignación = -1. Entonces, disminuya la string de prefijo. S = “aacb”.
Para prefijo de longitud 3: carácter máximo = ‘c’, asignación = 1. Por lo tanto, incremente la string de prefijo. S=”bbdb”.
Para prefijo de longitud 4: carácter máximo = ‘d’, asignación = 1. Por lo tanto, incremente la string de prefijo. S = “ccec”.

Enfoque: La solución se basa en el enfoque codicioso . Siga los pasos a continuación para resolver este problema:

1. Ejecute un bucle de i = 0 a i < N y en ese bucle ejecute otro bucle de j = i a j >= 0 (para atravesar el prefijo).
2. Ahora encuentre el elemento máximo en ese prefijo y el número al que se ha asignado en Dict , digamos mp .
3. Luego aplique la operación de incremento o decremento de acuerdo al número mp .
4. Ahora, cree un vector ans para almacenar la frecuencia de cada elemento.
5. Atraviese toda la string y rellene el vector ans .
6. Imprime los elementos del vector ans .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the frequency of
// all character after performing N operations
void 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 code
int 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 program for the above approach
import 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

# Python program for the above approach
 
# Function to find the frequency of
# all character after performing N operations
def 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 code
if __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# program for the above approach
using 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

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 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)