Descifrar las coordenadas del mapa de un par de strings dadas según las reglas dadas

Dado un par de strings en minúsculas string1[] y string2[] de tamaño M y N, la tarea es descifrar estas strings de acuerdo con las siguientes reglas. El último carácter de la string cifrada denota la dirección string de latitud (solo dos [ n-Norte, s-Sur ]) string de longitud (otras dos [ e-Este, w-Oeste ]). Excepto por el último carácter, la string denota un valor entero independientemente de si se trata de una string de latitud o de longitud. La parte entera de la coordenada se puede decodificar como ( Recuento de letras con el máximo de ocurrencias – Recuento de letras con el mínimo de ocurrencias en la string ). 

Ejemplos:

Entrada: string1[] = “babbeddcs”, string2[] = “aeeaecacw”
Salida: 2 Sur 1 Oeste
Explicación: En la string1, el último carácter es s, por lo que al sur, el carácter más frecuente es b con frecuencia 3 y la menor son a, eyc con 1. Del mismo modo, para la otra string, es decir, string2.

Entrada: string1[] = “ddcs”, string2[] = “aeew”
Salida: 1 Sur 1 Oeste

Enfoque: La idea para resolver este problema es contar la frecuencia máxima y mínima de caracteres de cada string y verificar el último carácter. Siga los pasos a continuación para resolver este problema:

• Inicialice las variables c1 y c2 como los últimos caracteres de las strings string1[] y string2[].
• Inicialice los vectores f1[26] y f2[26] con 0 para almacenar las frecuencias.
• Recorra las strings string1[] y string2[] y almacene la frecuencia de todos los caracteres de la string en los vectores f1[] y f2[].
• Inicialice las variables ma1, mi1, ma2 y mi2 para almacenar los caracteres de frecuencia máxima y mínima de las strings string1[] y string2[] .
• Recorra los vectores f1[] y f2[] y almacene los valores de ma1, mi1, ma2 y mi2.
• Después de realizar los pasos anteriores, imprima el resultado de los cálculos anteriores.

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 decrypt the strings
void find(string string1, string string2)
{
 
    // Size of the strings
    int M = string1.length(),
        N = string2.length();
 
    // Last characters of the strings
    char c1 = string1[M - 1],
         c2 = string2[N - 1];
 
    // Arrays to store the frequencies
    vector<int> f1(26, 0), f2(26, 0);
 
    // Calculate the frequency of characters
    // of both the strings
    for (int i = 0; i < M - 1; i++)
        f1[string1[i] - 'a']++;
 
    for (int i = 0; i < N - 1; i++)
        f2[string2[i] - 'a']++;
 
    // Variables to store the maximum and
    // minimum occurring character.
    int ma1 = 0, mi1 = M, ma2 = 0, mi2 = N;
 
    for (int i = 0; i < 26; i++) {
        ma1 = max(ma1, f1[i]);
        if (f1[i] > 0)
            mi1 = min(mi1, f1[i]);
 
        ma2 = max(ma2, f2[i]);
        if (f2[i] > 0)
            mi2 = min(mi2, f2[i]);
    }
 
    // Print the result
    cout << ma1 - mi1 << " ";
    if (c1 == 's')
        cout << "South ";
    else
        cout << "North ";
    cout << ma2 - mi2;
    if (c2 == 'e')
        cout << " East ";
    else
        cout << " West ";
}
 
// Driver Code
int main()
{
 
    string string1 = "babbeddcs",
           string2 = "aeeaecacw";
 
    find(string1, string2);
 
    return 0;
}

// Java code for the above approach
import java.io.*;
class GFG
{
   
// Function to decrypt the strings
static void find(String string1, String string2)
{
 
    // Size of the strings
    int M = string1.length();
    int N = string2.length();
 
    // Last characters of the strings
    char c1 = string1.charAt(M - 1);
    char c2 = string2.charAt(N - 1);
 
    // Arrays to store the frequencies
    int []f1 = new int[26];
    int []f2 = new int[26];
 
    // Calculate the frequency of characters
    // of both the strings
    for (int i = 0; i < M - 1; i++)
        f1[string1.charAt(i) - 'a']++;
 
    for (int i = 0; i < N - 1; i++)
        f2[string2.charAt(i) - 'a']++;
 
    // Variables to store the maximum and
    // minimum occurring character.
    int ma1 = 0, mi1 = M, ma2 = 0, mi2 = N;
 
    for (int i = 0; i < 26; i++) {
        ma1 = Math.max(ma1, f1[i]);
        if (f1[i] > 0)
            mi1 = Math.min(mi1, f1[i]);
 
        ma2 = Math.max(ma2, f2[i]);
        if (f2[i] > 0)
            mi2 = Math.min(mi2, f2[i]);
    }
 
    // Print the result
   System.out.print(ma1 - mi1 + " ");
    if (c1 == 's')
       System.out.print("South ");
    else
        System.out.print( "North ");
  System.out.print(ma2 - mi2);
    if (c2 == 'e')
        System.out.print( " East ");
    else
        System.out.print( " West ");
}
 
// Driver Code
    public static void main (String[] args) {
         String string1 = "babbeddcs";
         String string2 = "aeeaecacw";
 
       find(string1, string2);
       
    }
}
 
// This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Function to decrypt the strings
def find(string1, string2):
 
    # Size of the strings
    M = len(string1)
    N = len(string2)
 
    # Last characters of the strings
    c1 = string1[M - 1]
    c2 = string2[N - 1]
 
    # Arrays to store the frequencies
    f1 = [0 for _ in range(26)]
    f2 = [0 for _ in range(26)]
 
    # Calculate the frequency of characters
    # of both the strings
    for i in range(0, M - 1):
        f1[ord(string1[i]) - ord('a')] += 1
 
    for i in range(0, N - 1):
        f2[ord(string2[i]) - ord('a')] += 1
 
    # Variables to store the maximum and
    # minimum occurring character.
    ma1 = 0
    mi1 = M
    ma2 = 0
    mi2 = N
 
    for i in range(0, 26):
        ma1 = max(ma1, f1[i])
        if (f1[i] > 0):
            mi1 = min(mi1, f1[i])
 
        ma2 = max(ma2, f2[i])
        if (f2[i] > 0):
            mi2 = min(mi2, f2[i])
 
    # Print the result
    print(ma1 - mi1, end = " ")
    if (c1 == 's'):
        print("South", end = " ")
    else:
        print("North", end = " ")
 
    print(ma2 - mi2, end = "")
    if (c2 == 'e'):
        print(" East ", end = "")
    else:
        print(" West ")
 
# Driver Code
if __name__ == "__main__":
 
    string1 = "babbeddcs"
    string2 = "aeeaecacw"
 
    find(string1, string2)
 
# This code is contributed by rakeshsahni

// C# Program to implement
// the above approach
using System;
class GFG
{
// Function to decrypt the strings
static void find(string string1, string string2)
{
 
    // Size of the strings
    int M = string1.Length;
    int N = string2.Length;
 
    // Last characters of the strings
    char c1 = string1[M - 1];
    char c2 = string2[N - 1];
 
    // Arrays to store the frequencies
    int []f1 = new int[26];
    int []f2 = new int[26];
    for(int i = 0; i < 26; i++) {
        f1[i] = 0;
        f2[i] = 0;
    }
 
    // Calculate the frequency of characters
    // of both the strings
    for (int i = 0; i < M - 1; i++)
        f1[string1[i] - 'a']++;
 
    for (int i = 0; i < N - 1; i++)
        f2[string2[i] - 'a']++;
 
    // Variables to store the maximum and
    // minimum occurring character.
    int ma1 = 0, mi1 = M, ma2 = 0, mi2 = N;
 
    for (int i = 0; i < 26; i++) {
        ma1 = Math.Max(ma1, f1[i]);
        if (f1[i] > 0)
            mi1 = Math.Min(mi1, f1[i]);
 
        ma2 = Math.Max(ma2, f2[i]);
        if (f2[i] > 0)
            mi2 = Math.Min(mi2, f2[i]);
    }
 
    // Print the result
    Console.Write(ma1 - mi1 + " ");
    if (c1 == 's')
        Console.Write("South ");
    else
        Console.Write("North ");
    Console.Write(ma2 - mi2);
    if (c2 == 'e')
        Console.Write(" East ");
    else
        Console.Write(" West ");
}
 
// Driver code
public static void Main() {
     
    string string1 = "babbeddcs";
    string string2 = "aeeaecacw";
 
    find(string1, string2);
}
}
// This code is contributed by Samim Hossain Mondal.

<script>
// Javascript program for the above approach
 
// Function to decrypt the strings
function find(string1, string2)
{
 
    // Size of the strings
    let M = string1.length;
    let N = string2.length;
 
    // Last characters of the strings
    let c1 = string1[M - 1];
    let c2 = string2[N - 1];
 
    // Arrays to store the frequencies
    let f1 = [], f2 = [];
    for(let i = 0; i < 26; i++) {
        f1[i] = 0;
        f2[i] = 0;
    }
     
    // Calculate the frequency of characters
    // of both the strings
    for (let i = 0; i < M - 1; i++)
        f1[string1.charCodeAt(i) - 97]++;
 
    for (let i = 0; i < N - 1; i++)
        f2[string2.charCodeAt(i) - 97]++;
 
    // Variables to store the maximum and
    // minimum occurring character.
    let ma1 = 0, mi1 = M, ma2 = 0, mi2 = N;
 
    for (let i = 0; i < 26; i++) {
        ma1 = Math.max(ma1, f1[i]);
        if (f1[i] > 0)
            mi1 = Math.min(mi1, f1[i]);
 
        ma2 = Math.max(ma2, f2[i]);
        if (f2[i] > 0)
            mi2 = Math.min(mi2, f2[i]);
    }
 
    // Print the result
    document.write(ma1 - mi1 + " ");
    if (c1 == 's')
        document.write("South ");
    else
        document.write("North ");
    document.write(ma2 - mi2);
    if (c2 == 'e')
        document.write(" East ");
    else
        document.write(" West ");
}
 
// Driver Code
let string1 = "babbeddcs";
let string2 = "aeeaecacw";
 
find(string1, string2);
 
// This code is contributed by Samim Hossain Mondal.
</script>

2 South 1 West

Complejidad de tiempo: O(max(M, N))
Espacio auxiliar: O(1)