Movimiento mínimo para finalizar las operaciones para que todas las strings sean iguales

Dadas n strings que son permutaciones entre sí. Necesitamos hacer que todas las strings sean iguales con una operación que tome el carácter frontal de cualquier string y lo mueva al final.

Ejemplos: 

Input : n = 2
        arr[] = {"molzv", "lzvmo"}
Output : 2
Explanation: In first string, we remove
first element("m") from first string and 
append it end. Then we move second character
of first string and move it to end. So after
2 operations, both strings become same.

Input : n = 3
        arr[] = {"kc", "kc", "kc"}
Output : 0
Explanation: already all strings are equal.

El movimiento para finalizar la operación es básicamente una rotación a la izquierda. Usamos el enfoque discutido en verificar si las strings son rotaciones entre sí o no para contar una cantidad de operaciones de movimiento al frente requeridas para hacer que dos strings sean iguales. Consideramos una por una cada string como la string de destino. Contamos las rotaciones requeridas para hacer que todas las demás strings sean iguales al objetivo actual y finalmente devolvemos un mínimo de todos los conteos.

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

// CPP program to make all strings same using
// move to end operations.
#include <bits/stdc++.h>
using namespace std;
 
// Returns minimum number of moves to end
// operations to make all strings same.
int minimunMoves(string arr[], int n)
{
    int ans = INT_MAX;
    for (int i = 0; i < n; i++)
    {
        int curr_count = 0; 
 
        // Consider s[i] as target string and
        // count rotations required to make
        // all other strings same as str[i].
        for (int j = 0; j < n; j++) {
 
            string tmp = arr[j] + arr[j];
 
            // find function returns the index where we
            // found arr[i] which is actually count of
            // move-to-front operations.
            int index = tmp.find(arr[i]);
 
            // If any two strings are not rotations of
            // each other, we can't make them same. 
            if (index == string::npos)
                return -1;
 
            curr_count += index;
        }
 
        ans = min(curr_count, ans);
    }
 
    return ans;
}
 
// driver code for above function.
int main()
{
    string arr[] = {"xzzwo", "zwoxz", "zzwox", "xzzwo"}; 
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << minimunMoves(arr, n);
    return 0;
}

// Java program to make all
// strings same using move
// to end operations.
import java.util.*;
class GFG
{
 
// Returns minimum number of
// moves to end operations
// to make all strings same.
static int minimunMoves(String arr[], int n)
{
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++)
    {
        int curr_count = 0;
 
        // Consider s[i] as target
        // string and count rotations
        // required to make all other
        // strings same as str[i].
        String tmp = "";
        for (int j = 0; j < n; j++)
        {
            tmp = arr[j] + arr[j];
 
            // find function returns the
            // index where we found arr[i]
            // which is actually count of
            // move-to-front operations.
            int index = tmp.indexOf(arr[i]);
 
            // If any two strings are not
            // rotations of each other,
            // we can't make them same.
            if (index != -1)
                curr_count += index;
            else
                curr_count = -1; 
        }
 
        ans = Math.min(curr_count, ans);
    }
 
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    String arr[] = {"xzzwo", "zwoxz",
                    "zzwox", "xzzwo"};
    int n = arr.length;
    System.out.println(minimunMoves(arr, n));
}
}
 
// This code is contributed
// by Kirti_Mangal

# Python 3 program to make all strings
# same using move to end operations.
import sys
 
# Returns minimum number of moves to end
# operations to make all strings same.
def minimunMoves(arr, n):
 
    ans = sys.maxsize
    for i in range(n):
 
        curr_count = 0
 
        # Consider s[i] as target string and
        # count rotations required to make
        # all other strings same as str[i].
        for j in range(n):
 
            tmp = arr[j] + arr[j]
 
            # find function returns the index where
            # we found arr[i] which is actually
            # count of move-to-front operations.
            index = tmp.find(arr[i])
 
            # If any two strings are not rotations of
            # each other, we can't make them same.
            if (index == len(arr[i])):
                return -1
 
            curr_count += index
 
        ans = min(curr_count, ans)
 
    return ans
 
# Driver Code
if __name__ == "__main__":
     
    arr = ["xzzwo", "zwoxz", "zzwox", "xzzwo"]
    n = len(arr)
    print( minimunMoves(arr, n))
 
# This code is contributed by ita_c

using System;
 
// C# program to make all
// strings same using move
// to end operations.
public class GFG
{
 
// Returns minimum number of
// moves to end operations
// to make all strings same.
public  static int minimunMoves(string[] arr, int n)
{
    int ans = int.MaxValue;
    for (int i = 0; i < n; i++)
    {
        int curr_count = 0;
 
        // Consider s[i] as target
        // string and count rotations
        // required to make all other
        // strings same as str[i].
        string tmp = "";
        for (int j = 0; j < n; j++)
        {
            tmp = arr[j] + arr[j];
 
            // find function returns the
            // index where we found arr[i]
            // which is actually count of
            // move-to-front operations.
            int index = tmp.IndexOf(arr[i], StringComparison.Ordinal);
 
            // If any two strings are not
            // rotations of each other,
            // we can't make them same.
            if (index == arr[i].Length)
            {
                return -1;
            }
 
            curr_count += index;
        }
 
        ans = Math.Min(curr_count, ans);
    }
 
    return ans;
}
 
// Driver code
public static void Main(string[] args)
{
    string[] arr = new string[] {"xzzwo", "zwoxz", "zzwox", "xzzwo"};
    int n = arr.Length;
    Console.WriteLine(minimunMoves(arr, n));
}
}
 
// This code is contributed by Shrikant13

<script>
 
// Javascript program to make all
// strings same using move
// to end operations.
     
    // Returns minimum number of
    // moves to end operations
    // to make all strings same.
    function minimunMoves(arr,n)
    {
        let ans = Number.MAX_VALUE;
    for (let i = 0; i < n; i++)
    {
        let curr_count = 0;
   
        // Consider s[i] as target
        // string and count rotations
        // required to make all other
        // strings same as str[i].
        let tmp = "";
        for (let j = 0; j < n; j++)
        {
            tmp = arr[j] + arr[j];
   
            // find function returns the
            // index where we found arr[i]
            // which is actually count of
            // move-to-front operations.
            let index = tmp.indexOf(arr[i]);
   
            // If any two strings are not
            // rotations of each other,
            // we can't make them same.
            if (index == arr[i].length)
                return -1;
                   
            curr_count += index;
        }
   
        ans = Math.min(curr_count, ans);
    }
   
    return ans;
    }
     
    // Driver code
    let arr=["xzzwo", "zwoxz",
                    "zzwox", "xzzwo"];
    let n = arr.length;
    document.write(minimunMoves(arr, n));
    
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

5

Complejidad de tiempo : O(n ³ ) , donde n es el tamaño de la string dada (n ² para los dos bucles for anidados y n es para la función utilizada como find())
Espacio auxiliar: O(n)

Este artículo es una contribución de Pawan Asipu . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.