Repetir la última aparición de cada carácter alfanumérico en su posición en tiempos de familia de caracteres

Dada una string str[] de tamaño N , la tarea es codificarla de tal manera que la última aparición de cada carácter ocurra mientras su posición en su familia. Como ‘a’ es el primer carácter de su familia (alfabeto en minúsculas), seguirá siendo ‘a’, pero ‘b’ se convierte en ‘bb’, ‘D’ se convierte en ‘DDDD’ y así sucesivamente. En el caso de caracteres numéricos, el carácter aparece tantas veces como su valor. Como ‘1’ sigue siendo ‘1’, ‘2’ se convierte en ’22’, ‘0’ se convierte en ” y así sucesivamente. Pero aparte de la última aparición de un personaje, el resto debe permanecer como está. Los caracteres distintos de (az), (AZ) y (0-9) no se ven afectados por dicha codificación.

Ejemplos:

Entrada: str = “3bC”
​​Salida: 333bbCCC
Explicación: En la string dada, no se repite ningún carácter, por lo tanto, todos los caracteres tienen una ocurrencia que obviamente es la última. Entonces cada carácter será codificado. Como ‘3’ es un carácter numérico que tiene el valor 3, aparecerá tres veces en la string resultante. ‘b’ es el segundo carácter de su familia, por lo que aparecerá dos veces. Y ‘C’ es el tercer carácter de mayúscula, por lo que aparecerá tres veces.

Entrada: str = “Ea2, 0, E”
Salida: Ea22,, EEEEE
Explicación: ‘E’ al principio no es su última aparición en la string, por lo que permanecerá como está en la string resultante. Si bien ‘a’ y ‘2’ son sus únicas y últimas apariciones en la string, se cambiarán a ‘a’ y ’22’ respectivamente. Los caracteres ‘, ‘ y ‘ ‘ no se verán afectados. Y ‘0’ también se cambiará a ”.

Enfoque: Recorra la string y realice un seguimiento de la última aparición de cada carácter utilizando hashing y luego codifique para la última aparición. 
Siga los pasos a continuación para resolver el problema:

• Inicialice la string variable res como una string vacía para almacenar el resultado.
• Inicialice las arrays small y capital de tamaño 26 y num de tamaño 10 con 0 para almacenar la última aparición de cualquier carácter en la string str[].
• Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
  • Si str[i] es mayor que igual a ‘0’ y menor que igual a ‘9’ , entonces establezca el valor de num[str[i] – ‘0’] como i.
  • De lo contrario, si str[i] es mayor que igual a ‘a’ y menor que igual a ‘z’ , establezca el valor de small[str[i] – ‘a’] como i.
  • De lo contrario, si str[i] es mayor que igual a ‘A’ y menor que igual a ‘Z’ , establezca el valor de capital[str[i] – ‘A’] como i.
• Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
  • Si str[i] es mayor que igual a ‘0’ y menor que igual a ‘9’ y num[str[i]-‘0’] es igual a i , entonces inicialice la variable como str [i]-‘ 0’ y agregue str[i] en la string resultante res, ocurra varias veces.
  • De lo contrario, si str[i] es mayor que igual a ‘a’ y menor que igual a ‘z’ y small[str[i]-‘a’] es igual a i , entonces inicialice la variable como str [i]- ‘a’ y agrega str[i] en la string resultante res, ocurren varias veces.
  • De lo contrario, si str[i] es mayor que igual a ‘A’ y menor que igual a ‘Z’ y capital[str[i]-‘0’] es igual a i , entonces inicialice la variable como str [i]- ‘A’ y agrega str[i] en la string resultante res, ocurren varias veces.
  • De lo contrario, agregue str[i] en la string resultante res.
• Después de realizar los pasos anteriores, imprima la string res como respuesta.

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 encode the given string
void encodeString(string str)
{
 
    // Variable string to store the result
    string res = "";
 
    // Arrays to store the last occurring index
    // of every character in the string
    int small[26] = { 0 }, capital[26] = { 0 },
        num[10] = { 0 };
 
    // Length of the string
    int n = str.size();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // If str[i] is between 0 and 9
        if (str[i] >= '0' && str[i] <= '9') {
            num[str[i] - 48] = i;
        }
 
        // If str[i] is between a and z
        else if (str[i] >= 'a' && str[i] <= 'z') {
            small[str[i] - 97] = i;
        }
 
        // If str[i] is between A and Z
        else if (str[i] >= 'A' && str[i] <= 'Z') {
            capital[str[i] - 65] = i;
        }
    }
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // If str[i] is between a and z and i
        // is the last occurrence in str
        if ((str[i] >= 'a' && str[i] <= 'z')
            && small[str[i] - 97] == i) {
 
            int occ = str[i] - 96;
            while (occ--) {
                res += str[i];
            }
        }
 
        // If str[i] is between A and Z and i
        // is the last occurrence in str
        else if ((str[i] >= 'A' && str[i] <= 'Z')
                 && capital[str[i] - 65] == i) {
 
            int occ = str[i] - 64;
            while (occ--) {
                res += str[i];
            }
        }
 
        // If str[i] is between 0 and 9 and i
        // is the last occurrence in str
        else if ((str[i] >= '0' && str[i] <= '9')
                 && num[str[i] - 48] == i) {
 
            int occ = str[i] - 48;
            while (occ--) {
                res += str[i];
            }
        }
        else {
            res += str[i];
        }
    }
 
    // Print the result
    cout << res;
}
 
// Driver Code
int main()
{
    string str = "Ea2, 0, E";
 
    encodeString(str);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
   
// Function to encode the given string
static void encodeString(String str)
{
    // Variable string to store the result
    String res = "";
   
    // Arrays to store the last occurring index
    // of every character in the string
    int small[] = new int[26];
    int capital[] = new int[26];
    int num[] = new int[10];
        for(int i = 0; i < 26; i++)
        {
            small[i] = 0;
            capital[i] = 0;
        }
        for(int i = 0; i < 10; i++)
        {
            num[i] = 0;
        }
   
    // Length of the string
    int n = str.length();
   
    // Iterate over the range
    for (int i = 0; i < n; i++)
    {
   
        // If str[i] is between 0 and 9
        if (str.charAt(i)>= '0' && str.charAt(i) <= '9')
        {
            num[str.charAt(i) - 48] = i;
        }
   
        // If str[i] is between a and z
        else if (str.charAt(i) >= 'a' && str.charAt(i)<= 'z') {
            small[str.charAt(i)- 97] = i;
        }
   
        // If str[i] is between A and Z
        else if (str.charAt(i)>= 'A' && str.charAt(i) <= 'Z') {
            capital[str.charAt(i)- 65] = i;
        }
    }
   
    // Iterate over the range
    for (int i = 0; i < n; i++) {
   
        // If str[i] is between a and z and i
        // is the last occurrence in str
        if ((str.charAt(i)>= 'a' && str.charAt(i)<= 'z')
            && small[str.charAt(i)- 97] == i) {
   
            int occ = str.charAt(i) - 96;
            while (occ-- >0)
            {
                res += str.charAt(i);
            }
        }
   
        // If str[i] is between A and Z and i
        // is the last occurrence in str
        else if ((str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') && capital[str.charAt(i)- 65] == i)
        {
   
            int occ = str.charAt(i) - 64;
            while (occ-- >0) {
                res = res+str.charAt(i);
            }
        }
   
        // If str[i] is between 0 and 9 and i
        // is the last occurrence in str
        else if ((str.charAt(i)>= '0' && str.charAt(i) <= '9')
                 && num[str.charAt(i) - 48] == i) {
   
            int occ = str.charAt(i) - 48;
            while (occ-- >0) {
                res = res+str.charAt(i);
            }
        }
        else {
            res = res+str.charAt(i);
        }
    }
   
    // Print the result
    System.out.print(res);
}
 
    // Driver Code
    public static void main(String[] args)
    {
            String str = "Ea2, 0, E";
   
              encodeString(str);
    }
}
 
// This code is contributed by dwivediyash

# Python 3 program for the above approach
 
# Function to encode the given string
def encodeString(str):
   
    # Variable string to store the result
    res = ""
 
    # Arrays to store the last occurring index
    # of every character in the string
    small = [0 for i in range(26)]
    capital = [0 for i in range(26)]
    num = [0 for i in range(10)]
 
    # Length of the string
    n = len(str)
 
    # Iterate over the range
    for i in range(n):
        # If str[i] is between 0 and 9
        if (str[i] >= '0' and str[i] <= '9'):
            num[ord(str[i]) - 48] = i
 
        # If str[i] is between a and z
        elif(str[i] >= 'a' and str[i] <= 'z'):
            small[ord(str[i]) - 97] = i
 
        # If str[i] is between A and Z
        elif(str[i] >= 'A' and str[i] <= 'Z'):
            capital[ord(str[i]) - 65] = i
 
    # Iterate over the range
    for i in range(n):
       
        # If str[i] is between a and z and i
        # is the last occurrence in str
        if ((str[i] >= 'a' and str[i] <= 'z') and small[ord(str[i]) - 97] == i):
            occ = ord(str[i]) - 96
            while(occ>0):
                res += str[i]
                occ -= 1
 
        # If str[i] is between A and Z and i
        # is the last occurrence in str
        elif((str[i] >= 'A' and str[i] <= 'Z') and capital[ord(str[i]) - 65] == i):
            occ = ord(str[i]) - 64
            while (occ>0):
                res += str[i]
                occ -= 1
 
        # If str[i] is between 0 and 9 and i
        # is the last occurrence in str
        elif((str[i] >= '0' and str[i] <= '9') and num[ord(str[i]) - 48] == i):
            occ = ord(str[i]) - 48
            while (occ>0):
                res += str[i]
                occ -= 1
        else:
            res += str[i]
 
    # Print the result
    print(res)
 
# Driver Code
if __name__ == '__main__':
    str = "Ea2, 0, E"
    encodeString(str)
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
using System;
 
public class GFG
{
 
  // Function to encode the given string
  static void encodeString(String str)
  {
 
    // Variable string to store the result
    String res = "";
 
    // Arrays to store the last occurring index
    // of every character in the string
    int []small = new int[26];
    int []capital = new int[26];
    int []num = new int[10];
    for(int i = 0; i < 26; i++)
    {
      small[i] = 0;
      capital[i] = 0;
    }
    for(int i = 0; i < 10; i++)
    {
      num[i] = 0;
    }
 
    // Length of the string
    int n = str.Length;
 
    // Iterate over the range
    for (int i = 0; i < n; i++)
    {
 
      // If str[i] is between 0 and 9
      if (str[i]>= '0' && str[i] <= '9')
      {
        num[str[i] - 48] = i;
      }
 
      // If str[i] is between a and z
      else if (str[i] >= 'a' && str[i]<= 'z') {
        small[str[i]- 97] = i;
      }
 
      // If str[i] is between A and Z
      else if (str[i]>= 'A' && str[i] <= 'Z') {
        capital[str[i]- 65] = i;
      }
    }
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
      // If str[i] is between a and z and i
      // is the last occurrence in str
      if ((str[i]>= 'a' && str[i]<= 'z')
          && small[str[i]- 97] == i) {
 
        int occ = str[i] - 96;
        while (occ-- >0)
        {
          res += str[i];
        }
      }
 
      // If str[i] is between A and Z and i
      // is the last occurrence in str
      else if ((str[i] >= 'A' && str[i] <= 'Z') && capital[str[i]- 65] == i)
      {
 
        int occ = str[i] - 64;
        while (occ-- >0) {
          res = res+str[i];
        }
      }
 
      // If str[i] is between 0 and 9 and i
      // is the last occurrence in str
      else if ((str[i]>= '0' && str[i] <= '9')
               && num[str[i] - 48] == i) {
 
        int occ = str[i] - 48;
        while (occ-- >0) {
          res = res+str[i];
        }
      }
      else {
        res = res+str[i];
      }
    }
 
    // Print the result
    Console.Write(res);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    String str = "Ea2, 0, E";
 
    encodeString(str);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to encode the given string
        function encodeString(str) {
 
            // Variable string to store the result
            let res = "";
 
            // Arrays to store the last occurring index
            // of every character in the string
            let small = new Array(26).fill(0), capital = new Array(26).fill(0),
                num = new Array(26).fill(0);
 
            // Length of the string
            let n = str.length;
 
            // Iterate over the range
            for (let i = 0; i < n; i++) {
 
                // If str[i] is between 0 and 9
                if (str[i].charCodeAt(0) >= '0'.charCodeAt(0) && str[i].charCodeAt(0) <= '9'.charCodeAt(0)) {
                    num[str[i].charCodeAt(0) - 48] = i;
                }
 
                // If str[i] is between a and z
                else if (str[i].charCodeAt(0) >= 'a'.charCodeAt(0) && str[i].charCodeAt(0) <= 'z'.charCodeAt(0)) {
                    small[str[i].charCodeAt(0) - 97] = i;
                }
 
                // If str[i] is between A and Z
                else if (str[i].charCodeAt(0) >= 'A'.charCodeAt(0) && str[i].charCodeAt(0) <= 'Z'.charCodeAt(0)) {
                    capital[str[i].charCodeAt(0) - 65] = i;
                }
            }
 
            // Iterate over the range
            for (let i = 0; i < n; i++) {
 
                // If str[i] is between a and z and i
                // is the last occurrence in str
                if ((str[i].charCodeAt(0) >= 'a'.charCodeAt(0) && str[i].charCodeAt(0) <= 'z'.charCodeAt(0))
                    && small[str[i].charCodeAt(0) - 97] == i) {
 
                    let occ = str[i].charCodeAt(0) - 96;
                    while (occ--) {
                        res += str[i];
                    }
                }
 
                // If str[i] is between A and Z and i
                // is the last occurrence in str
                else if ((str[i].charCodeAt(0) >= 'A'.charCodeAt(0) && str[i].charCodeAt(0) <= 'Z'.charCodeAt(0))
                    && capital[str[i].charCodeAt(0) - 65] == i) {
 
                    let occ = str[i].charCodeAt(0) - 64;
                    while (occ--) {
                        res += str[i];
                    }
                }
 
                // If str[i] is between 0 and 9 and i
                // is the last occurrence in str
                else if ((str[i].charCodeAt(0) >= '0'.charCodeAt(0) && str[i].charCodeAt(0) <= '9'.charCodeAt(0))
                    && num[str[i].charCodeAt(0) - 48] == i) {
 
                    let occ = str[i].charCodeAt(0) - 48;
                    while (occ--) {
                        res += str[i];
                    }
                }
                else {
                    res += str[i];
                }
            }
 
            // Print the result
            document.write(res);
        }
 
        // Driver Code
        let str = "Ea2, 0, E";
        encodeString(str);
 
// This code is contributed by Potta Lokesh
    </script>

Ea22, , EEEEE

Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(M) (Tamaño de la string resultante)