Ordenar una array de strings por reemplazos con su GCD con elementos de otra array

Dados dos arreglos de strings arr[] y k[] de tamaño N y M respectivamente, la tarea es ordenar el arreglo arr[] después de reemplazar cada elemento del arreglo arr[i] con el GCD de arr[i] y k[j ], donde 0 ≤ i < N y 0 ≤ j < M. Si no es posible ordenar la array, imprima -1 .

Nota: El GCD de dos strings A y B es la string más pequeña, que cuando se concatena varias veces , se vuelve igual a A y B. Si no existe tal string, devuelve una string vacía.

Ejemplos:

Entrada:   arr[] = { ‘geeks’, ‘for’, ‘geeks’ }, k[] = { ‘geeksgeeks’, ‘for’ }
Salida:  { ‘ ‘, ‘for’, ‘geeks’ }
Explicación: 
arr [0] = GCD(‘geeks’, ‘for’) = ‘ ‘
arr[1] = GCD(‘for’, ‘for’) = ‘for’
arr[2] = GCD(‘geeks’, ‘geeksgeeks’ ) = ‘geeks’ 
arr[0] < arr[1] < arr[2]

Entrada:   arr[] = { ‘aacd’, ‘abdc’, ‘acac’, ‘aaaa’ }, k[] = {‘aa’, ‘ac’}
Salida: -1

Enfoque: El problema dado se puede resolver con avidez . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos, prev = ” ( string vacía ), para almacenar la string anterior en el orden ordenado.
• Atraviesa la array , para i en el rango [0, N – 1]
  • Calcule el GCD con cada string de arr[i] con k[j], para j en el rango [0, M – 1] .
  • Encuentre la string mínima, digamos, optEle lexicográficamente mayor que anterior
  • Actualizar arr[i] = optEle
  • Actualizar anterior = arr[i]
• Si la array está ordenada en orden ascendente . Imprime la array
• De lo contrario, imprima -1.

A continuación se muestra la implementación.

# Python implementation of the
# above approach
 
# Function to find gcd of two numbers
def GCD(a, b):
    if(b == 0):
        return a
    else:
        return GCD(b, a % b)
 
 
# Function to find GCD of two strings
def StringGCD(a, b):
     
    # Length of gcd of two strings
    gcd = GCD(len(a), len(b))
     
    if a[:gcd] == b[:gcd]:
        if a*(len(b)//gcd) == b*(len(a)//gcd):
            return a[:gcd]
     
    # GCD of strings does not exist
    return ' '
 
# Function to check if the array is
# sorted in increasing order or not
def isIncreasing(arr):
   
    for i in range(len(arr)-1):
        if arr[i] >= arr[i + 1]:
            return False
           
    return True
 
# Function to check if arr[] can
# be sorted in increasing order
def sortByGcd(arr, k):
   
      # Previous string
    prev = ''
     
    # Iterate through the array
    for i in range(len(arr)):
       
        # Initialize optimal
        # element by arr[i]
        optEle = arr[i]
         
        # Flag to find first
        # string > prev
        flag = True
         
        for idx in range(len(k)):
           
            # Gcd of two strings
            Ele = StringGCD(arr[i], k[idx])
             
            # If Ele > prev and flag is set
            if Ele > prev and flag:
               
                  # Update optEle
                optEle = Ele
                 
                # Update Flag
                flag = False
             
            # If Ele > prev
            if Ele > prev:
                   
                # Update optEle
                optEle = min(optEle, Ele)
                 
        # Update arr[i] by optEle
        arr[i] = optEle
         
        # Update prev by arr[i]
        prev = arr[i]
         
    # Check is arr[] is sorted in ascending order
    if isIncreasing(arr):
        return arr
       
    # Sorted order is not possible
    else:
        return -1
 
 
# Driver Code
 
arr = ['geeks', 'for', 'geeks']
k = ['geeks', 'for']
print(sortByGcd(arr, k))

<script>
// Javascript implementation of the
// above approach
 
//  Function to find gcd of two numbers
function GCD(a, b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
 
// Function to find GCD of two strings 
function StringGCD(a, b) {
    if (a + b !== b + a) {
        // not possible
        // no common element
        return "";
    } else if (a == b) {
        return a;
    } else if (a.length > b.length) {
        return StringGCD(a.slice(str2.length), b);
    } else {
        return StringGCD(b.slice(str1.length), a);
    }
}
 
// Function to check if the array is
// sorted in increasing order or //not
function isIncreasing(arr) {
 
    for (let i = 0; i < (arr.length - 1); i++) {
        if (arr[i] >= arr[i + 1])
            return false;
    }
    return true;
}
 
// Function to check if arr[] can
// be sorted in increasing order
function sortByGcd(arr, k) {
 
    // Previous string
    var prev = "";
 
    // Iterate through the array
    for (let i = 0; i < (arr.length); i++) {
 
        // Initialize optimal
        // element by arr[i]
        optEle = arr[i];
 
        // Flag to find first
        // string > prev
        var flag = true;
 
        for (let idx = 0; idx < k.length; idx++) {
 
            // Gcd of two strings
            var Ele = StringGCD(arr[i], k[idx]);
 
            // If Ele > prev and flag is set
            if (Ele > prev && flag) {
 
                // Update optEle
                optEle = Ele;
 
                // Update Flag
                flag = false;
            }
            // If Ele > prev
            if (Ele > prev) {
 
                // Update optEle
                optEle = Math.min(optEle, Ele);
            }
        }
         
        // Update arr[i] by optEle
        if (isNaN(optEle)) {
            arr[i] = ' ';
        }
        else {
            arr[i] = optEle;
        }
        // Update prev by arr[i]
        prev = arr[i]
        // Check is arr[] is sorted in ascending order
        if (isIncreasing(arr)) {
            return arr;
        }
        // Sorted order is not possible
        else
            return -1;
    }
}
 
// Driver Code
var arr = ['geeks', 'for', 'geeks'];
var k = ['geeks', 'for'];
console.log(sortByGcd(arr, k));
 
// This code is contributed by akashish__
</script>

Complejidad de tiempo: O(N * K * log(min(N, K))
Espacio auxiliar: O(1)