Minimice el costo de convertir una string dada en una concatenación de substrings iguales de longitud K

Posted on by Rudeus Greyrat

Dada una string S de longitud N que consta de letras minúsculas y un número entero K , donde N % K = 0 , la tarea es encontrar el costo mínimo para convertir la string dada en una string concatenada de las mismas K substrings de longitud realizando el siguientes operaciones:

  • Un carácter puede ser reemplazado por otro carácter.
  • El costo de cada operación es la diferencia absoluta entre el personaje reemplazado y el reemplazado. Por ejemplo, si ‘a’ se reemplaza con ‘z’ , entonces el costo de la operación es |”a”-“z”| = 25 .

Ejemplos:

Entrada: S = “abcdef”, K = 2
Salida: 8
Explicación:
Una respuesta posible es “cdcdcd” y la substring de longitud k repetida es “cd”. El costo mínimo requerido para convertir la string se calcula mediante los siguientes pasos:
Paso 1: Reemplace S[0] con “c”. Por lo tanto, costo = |”a”-“c”| = 2.
Paso 2: Reemplace S[1] con “d”. Por tanto, coste = |”b”-“d”| = 2.
Paso 3: Reemplace S[2] con “c”. Por lo tanto, costo = |”c”-“c”| = 0.
Paso 4: Reemplace S[3] con “d”. Por lo tanto, costo = |”d”-“d”| = 0.
Paso 5: Reemplace S[4] con “c”. Por tanto, coste = |”e”-“c”| = 2.
Paso 6: Reemplace S[5] con “d”. Por tanto, coste = |”f”-“d”| = 2.
Por lo tanto, el costo mínimo requerido = 2 + 2 + 0 + 0 + 2 + 2 = 8.

Entrada: S = “abcabc”, K = 3
Salida: 0
Explicación:
La string dada ya consiste en una substring repetida “abc” de longitud K

Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones posibles de longitud K y encontrar el costo de convertir la string dada de modo que tenga un patrón repetitivo de longitud K . Luego, imprima el costo mínimo entre ellos. 

Complejidad de tiempo: O(N*K 26 ), donde N es la longitud de la string dada y K es el entero dado.
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es usar una técnica codiciosa y observar que para cualquier posición i de 0 a K – 1 , los caracteres en la posición i + j * K deben ser los mismos donde 0 ≤ j < N/K . Por ejemplo, si S = “abcbbc” y K = 3 , los caracteres en las posiciones 0 y 3 deben ser iguales, los caracteres en las posiciones 1 y 4 deben ser iguales y los caracteres en las posiciones 2 y 5 deben ser iguales. Por lo tanto, el costo mínimo de los caracteres en las posiciones i + j * Kse puede calcular individualmente. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable y almacene el costo mínimo requerido.
  • Atraviese la string sobre el rango [0, K – 1] .
  • Para cada posición i , encuentre el costo de colocar un carácter en las posiciones i + j * K , para cada carácter donde 0 ≤ j < N/K . Calcule el costo mínimo entre ellos y actualice ans .
  • Después de completar los pasos anteriores, imprima el valor de ans como el costo mínimo requerido.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum cost
// to convert given String into
// String of K length same subString
void minCost(string s, int k)
{
     
    // Stores length of String
    int n = s.size();
     
    // Stores the minimum cost
    int ans = 0;
 
    // Traverse left subString
    // of k length
    for(int i = 0; i < k; i++)
    {
         
        // Stores the frequency
        int a[26];
         
        for(int p = 0; p < 26; p++)
        {
            a[p] = 0;
        }
 
        for(int j = i; j < n; j += k)
        {
            a[s[j] - 'a']++;
        }
 
        // Stores minimum cost for
        // sequence of S[i]%k indices
        int min_cost = INT_MAX;
 
        // Check for optimal character
        for(int ch = 0; ch < 26; ch++)
        {
            int cost = 0;
 
            // Find sum of distance 'a'+ ch
            // from character S[i]%k indices
            for(int tr = 0; tr < 26; tr++)
                cost += abs(ch - tr) * a[tr];
 
            // Choose minimum cost for
            // each index i
            min_cost = min(min_cost, cost);
        }
         
        // Increment ans
        ans += min_cost;
    }
 
    // Print minimum cost to
    // convert String
    cout << (ans);
}
 
// Driver Code
int main()
{
     
    // Given String S
    string S = "abcdefabc";
 
    int K = 3;
 
    // Function Call
    minCost(S, K);
}
 
// This code is contributed by gauravrajput1

Java

// Java program for the above approach
 
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Function to find minimum cost
    // to convert given string into
    // string of K length same substring
    static void minCost(String s, int k)
    {
        // Stores length of string
        int n = s.length();
 
        // Stores the minimum cost
        int ans = 0;
 
        // Traverse left substring
        // of k length
        for (int i = 0; i < k; i++) {
 
            // Stores the frequency
            int[] a = new int[26];
 
            for (int j = i; j < n; j += k) {
                a[s.charAt(j) - 'a']++;
            }
 
            // Stores minimum cost for
            // sequence of S[i]%k indices
            int min_cost
                = Integer.MAX_VALUE;
 
            // Check for optimal character
            for (int ch = 0; ch < 26; ch++) {
 
                int cost = 0;
 
                // Find sum of distance 'a'+ ch
                // from character S[i]%k indices
                for (int tr = 0; tr < 26; tr++)
                    cost += Math.abs(ch - tr)
                            * a[tr];
 
                // Choose minimum cost for
                // each index i
                min_cost = Math.min(min_cost,
                                    cost);
            }
 
            // Increment ans
            ans += min_cost;
        }
 
        // Print minimum cost to
        // convert string
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given string S
        String S = "abcdefabc";
 
        int K = 3;
 
        // Function Call
        minCost(S, K);
    }
}

Python3

# Python3 program for the
# above approach
import sys
 
# Function to find minimum cost
# to convert given string into
# string of K length same substring
def minCost(s, k):
      
    # Stores length of string
    n = len(s)
  
    # Stores the minimum cost
    ans = 0
  
    # Traverse left substring
    # of k length
    for i in range(k):
          
        # Stores the frequency
        a = [0] * 26
  
        for j in range(i, n, k):
            a[ord(s[j]) - ord('a')] += 1
         
        # Stores minimum cost for
        # sequence of S[i]%k indices
        min_cost = sys.maxsize - 1
  
        # Check for optimal character
        for ch in range(26):
            cost = 0
              
            # Find sum of distance 'a'+ ch
            # from character S[i]%k indices
            for tr in range(26):
                cost += abs(ch - tr) * a[tr]
  
            # Choose minimum cost for
            # each index i
            min_cost = min(min_cost,
                               cost)
                                
        # Increment ans
        ans += min_cost
     
    # Print minimum cost to
    # convert string
    print(ans)
 
# Driver Code
      
# Given string S
S = "abcdefabc"
  
K = 3
  
# Function call
minCost(S, K)
 
# This code is contributed by code_hunt

C#

// C# program for the
// above approach
using System;
 
class GFG{
  
// Function to find minimum cost
// to convert given string into
// string of K length same substring
static void minCost(string s, int k)
{
     
    // Stores length of string
    int n = s.Length;
 
    // Stores the minimum cost
    int ans = 0;
 
    // Traverse left substring
    // of k length
    for(int i = 0; i < k; i++)
    {
         
        // Stores the frequency
        int[] a = new int[26];
 
        for(int j = i; j < n; j += k)
        {
            a[s[j] - 'a']++;
        }
 
        // Stores minimum cost for
        // sequence of S[i]%k indices
        int min_cost = Int32.MaxValue;
 
        // Check for optimal character
        for(int ch = 0; ch < 26; ch++)
        {
            int cost = 0;
             
            // Find sum of distance 'a'+ ch
            // from character S[i]%k indices
            for(int tr = 0; tr < 26; tr++)
                cost += Math.Abs(ch - tr) * a[tr];
 
            // Choose minimum cost for
            // each index i
            min_cost = Math.Min(min_cost,
                                cost);
        }
 
        // Increment ans
        ans += min_cost;
    }
 
    // Print minimum cost to
    // convert string
    Console.WriteLine(ans);
}
 
// Driver Code
public static void Main()
{
     
    // Given string S
    string S = "abcdefabc";
 
    int K = 3;
 
    // Function call
    minCost(S, K);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
// Javascript program for the above approach
 
// Function to find minimum cost
// to convert given String into
// String of K length same subString
function minCost(s, k)
{
     
    // Stores length of String
    var n = s.length;
     
    // Stores the minimum cost
    var ans = 0;
 
    // Traverse left subString
    // of k length
    for(var i = 0; i < k; i++)
    {
         
        // Stores the frequency
        var a = new Array(26).fill(0);
 
        for(var j = i; j < n; j += k)
        {
            a[s[j].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
 
        // Stores minimum cost for
        // sequence of S[i]%k indices
        var min_cost = 1000000000;
 
        // Check for optimal character
        for(var ch = 0; ch < 26; ch++)
        {
            var cost = 0;
 
            // Find sum of distance 'a'+ ch
            // from character S[i]%k indices
            for(var tr = 0; tr < 26; tr++)
                cost += Math.abs(ch - tr) * a[tr];
 
            // Choose minimum cost for
            // each index i
            min_cost = Math.min(min_cost, cost);
        }
         
        // Increment ans
        ans += min_cost;
    }
 
    // Print minimum cost to
    // convert String
    document.write(ans);
}
 
// Driver Code
// Given String S
var S = "abcdefabc";
var K = 3;
// Function Call
minCost(S, K);
 
</script>
Producción: 

9

 

Complejidad temporal: O(N + K)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *