Intercambios mínimos requeridos entre dos strings para hacer que una string sea estrictamente mayor que la otra

Posted on by Rudeus Greyrat

Dadas dos strings A y B de longitud M y N respectivamente, la tarea es encontrar el intercambio mínimo de dos caracteres requerido para hacer que la string A sea lexicográficamente mayor que la string B.

Ejemplos:

Entrada: A = “1432”, B = “789”, M = 4, N = 3
Salida: 1
Explicación:
Una forma posible es intercambiar caracteres en el índice 0 de ambas strings. Por lo tanto, A se modifica a “7432” y B se modifica a “189”.

Entrada: A = “3733”, B = “3333”, M = 4, N = 4
Salida: 2
Explicación:
Paso 1: Intercambiar el carácter en el índice 1 de la string A con el carácter en el índice 0 de la string B. Las strings A y B se modifican a «3333» y «7333».
Paso 2: Intercambie el carácter en el índice 0 de la string A con un carácter en el índice 0 de la string B. Las strings A y B se modifican a «7333» y «3333».

Planteamiento: Se puede observar que si M ≤ N y todos los caracteres son iguales, incluyendo ambas strings, entonces no es posible hacer que la string A sea estrictamente mayor que la string B. De lo contrario, la string A puede hacerse estrictamente mayor que la string B colocando los dos caracteres diferentes en el índice 0 de ambas strings en un máximo de dos movimientos.

Siga los pasos a continuación para resolver el problema:

  1. Primero, verifique si el primer carácter de la string A es mayor que el primer carácter de la string B y luego imprima 0 .
  2. De lo contrario, verifique si B[0] > A[0] , entonces se necesita 1 intercambio, así que intercambie A[0] con B[0] e imprima 1.
  3. De lo contrario, verifique si todos los caracteres son iguales en ambas strings y M ≤ N , entonces no es posible, así que imprima  -1 .
  4. De lo contrario, verifique si hay algún carácter en A que sea menor que A[0] o un carácter en B que sea mayor que B[0] y luego imprima  1 .
  5. De lo contrario, verifique si existe algún carácter en A que sea menor que A[0] o algún carácter en B que sea mayor que B[0] y luego imprima  2 .
  6. De lo contrario, devuelva 0 si no se cumple ninguna de las condiciones anteriores.

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 the minimum
// number of steps to make A > B
int minSteps(string A, string B, int M, int N)
{
 
    if (A[0] > B[0])
        return 0;
 
    if (B[0] > A[0]) {
        return 1;
    }
 
    // If all character are same and M <= N
    if (M <= N && A[0] == B[0]
        && count(A.begin(), A.end(), A[0]) == M
        && count(B.begin(), B.end(), B[0]) == N)
        return -1;
 
    // If there lies any character
    // in B which is greater than B[0]
    for (int i = 1; i < N; i++) {
 
        if (B[i] > B[0])
            return 1;
    }
 
    // If there lies any character
    // in A which is smaller than A[0]
    for (int i = 1; i < M; i++) {
 
        if (A[i] < A[0])
            return 1;
    }
 
    // If there lies a character which
    // is in A and greater than A[0]
    for (int i = 1; i < M; i++) {
 
        if (A[i] > A[0]) {
 
            swap(A[i], B[0]);
            swap(A[0], B[0]);
            return 2;
        }
    }
 
    // If there lies a character which
    // is in B and less than B[0]
    for (int i = 1; i < N; i++) {
 
        if (B[i] < B[0]) {
 
            swap(A[0], B[i]);
            swap(A[0], B[0]);
            return 2;
        }
    }
 
    // Otherwise
    return 0;
}
 
// Driver Code
int main()
{
    string A = "adsfd";
    string B = "dffff";
 
    int M = A.length();
    int N = B.length();
 
    cout << minSteps(A, B, M, N);
 
    return 0;
}

Java

// Java program for above approach
import java.util.*;
import java.lang.*;
class GFG
{
 
  // Function to find the minimum
  // number of steps to make A > B
  static int minSteps(StringBuilder A,
                      StringBuilder B,
                      int M, int N)
  {
 
    if (A.charAt(0) > B.charAt(0))
      return 0;
 
    if (B.charAt(0) > A.charAt(0))
    {
      return 1;
    }
 
    // If all character are same and M <= N
    if (M <= N && A.charAt(0) == B.charAt(0)
        && count(A, A.charAt(0)) == M
        && count(B, B.charAt(0)) == N)
      return -1;
 
    // If there lies any character
    // in B which is greater than B[0]
    for (int i = 1; i < N; i++)
    {
 
      if (B.charAt(i) > B.charAt(0))
        return 1;
    }
 
    // If there lies any character
    // in A which is smaller than A[0]
    for (int i = 1; i < M; i++)
    {
 
      if (A.charAt(i) < A.charAt(0))
        return 1;
    }
 
    // If there lies a character which
    // is in A and greater than A[0]
    for (int i = 1; i < M; i++)
    {
      if (A.charAt(i) > A.charAt(0))
      {
        swap(A, i, B, 0);
        swap(A, 0, B, 0);
        return 2;
      }
    }
 
    // If there lies a character which
    // is in B and less than B[0]
    for (int i = 1; i < N; i++)
    {
      if (B.charAt(i) < B.charAt(0))
      {
        swap(A, 0, B, i);
        swap(A, 0, B, 0);
        return 2;
      }
    }
 
    // Otherwise
    return 0;
  }
 
  static int count(StringBuilder a,
                   char c)
  {
    int count = 0;
    for(int i = 0; i < a.length(); i++)
      if(a.charAt(i) == c)
        count++; 
    return count;  
  }
 
  static void swap(StringBuilder s1,
                   int index1,
                   StringBuilder s2,
                   int index2)
  {
    char c = s1.charAt(index1);
    s1.setCharAt(index1,s2.charAt(index2));
    s2.setCharAt(index2,c);
 
  }
  // Driver function
  public static void main (String[] args)
  {
    StringBuilder A = new StringBuilder("adsfd");
    StringBuilder B = new StringBuilder("dffff");
    int M = A.length();
    int N = B.length();
    System.out.println(minSteps(A, B, M, N));
  }
}
 
// This code is contributed by offbeat.

Python3

# Python3 program for the above approach
 
# Function to find the minimum
# number of steps to make A > B
def minSteps(A, B, M, N):
     
    if (A[0] > B[0]):
        return 0
 
    if (B[0] > A[0]):
        return 1
 
    # If all character are same and M <= N
    if (M <= N and A[0] == B[0] and
           A.count(A[0]) == M and
           B.count(B[0]) == N):
        return -1
 
    # If there lies any character
    # in B which is greater than B[0]
    for i in range(1, N):
        if (B[i] > B[0]):
            return 1
 
    # If there lies any character
    # in A which is smaller than A[0]
    for i in range(1, M):
        if (A[i] < A[0]):
            return 1
 
    # If there lies a character which
    # is in A and greater than A[0]
    for i in range(1, M):
        if (A[i] > A[0]):
            A[0], B[i] = B[i], A[0]
            A[0], B[0] = B[0], A[0]
            return 2
 
    # If there lies a character which
    # is in B and less than B[0]
    for i in range(1, N):
        if (B[i] < B[0]):
            A[0], B[i] = B[i], A[0]
            A[0], B[0] = B[0], A[0]
            return 2
 
    # Otherwise
    return 0
 
# Driver Code
if __name__ == '__main__':
     
    A = "adsfd"
    B = "dffff"
 
    M = len(A)
    N = len(B)
 
    print(minSteps(A, B, M, N))
 
# This code is contributed by mohit kumar 29

C#

// C# program for above approach
using System;
using System.Text;
 
public class GFG
{
 
  // Function to find the minimum
  // number of steps to make A > B
  static int minSteps(StringBuilder A, StringBuilder B,  int M, int N)
  {
    if (A[0] > B[0])
      return 0;
 
    if (B[0] > A[0])
    {
      return 1;
    }
 
    // If all character are same and M <= N
    if (M <= N && A[0] == B[0]
        && count(A, A[0]) == M
        && count(B, B[0]) == N)
      return -1;
 
    // If there lies any character
    // in B which is greater than B[0]
    for (int i = 1; i < N; i++)
    {
 
      if (B[i] > B[0])
        return 1;
    }
 
    // If there lies any character
    // in A which is smaller than A[0]
    for (int i = 1; i < M; i++)
    {
 
      if (A[i] < A[0])
        return 1;
    }
 
    // If there lies a character which
    // is in A and greater than A[0]
    for (int i = 1; i < M; i++)
    {
      if (A[i] > A[0])
      {
        swap(A, i, B, 0);
        swap(A, 0, B, 0);
        return 2;
      }
    }
 
    // If there lies a character which
    // is in B and less than B[0]
    for (int i = 1; i < N; i++)
    {
      if (B[i] < B[0])
      {
        swap(A, 0, B, i);
        swap(A, 0, B, 0);
        return 2;
      }
    }
 
    // Otherwise
    return 0;
 
  }
 
  static int count(StringBuilder a,
                   char c)
  {
    int count = 0;
    for(int i = 0; i < a.Length; i++)
      if(a[i] == c)
        count++; 
    return count;  
  }
 
  static void swap(StringBuilder s1,
                   int index1,
                   StringBuilder s2,
                   int index2)
  {
 
    char c = s1[index1];
    s1[index1] = s2[index2];
    s2[index2] = c;
  }
 
  // Driver function
  static public void Main ()
  {
    StringBuilder A = new StringBuilder("adsfd");
    StringBuilder B = new StringBuilder("dffff");
    int M=A.Length;
    int N=B.Length;
    Console.WriteLine(minSteps(A, B, M, N));
  }
}
 
// This code is contributed by avanitrachhadiya2155

Javascript

<script>
//Javascript  program to implement
// the above approach
 
// Function to find the minimum
// number of steps to make A > B
function minSteps( A, B,M, N)
{
 
    if (A[0] > B[0])
    return 0;
 
    if (B[0] > A[0])
    {
        return 1;
    }
 
    // If all character are same and M <= N
    if (M <= N && A[0] == B[0] && count(A, A[0]) == M
        && count(B, B[0]) == N)
        return -1;
 
    // If there lies any character
    // in B which is greater than B[0]
    for (var i = 1; i < N; i++)
    {
 
        if (B[i] > B[0])
            return 1;
    }
 
    // If there lies any character
    // in A which is smaller than A[0]
    for (var i = 1; i < M; i++)
    {
 
        if (A[i] < A[0])
            return 1;
    }
 
    // If there lies a character which
    // is in A and greater than A[0]
    for (var i = 1; i < M; i++)
    {
        if (A[i] > A[0])
          {
            swap(A, i, B, 0);
            swap(A, 0, B, 0);
            return 2;
          }
    }
 
    // If there lies a character which
    // is in B and less than B[0]
    for (var i = 1; i < N; i++)
    {
        if (B[i] < B[0])
          {
            swap(A, 0, B, i);
            swap(A, 0, B, 0);
            return 2;
          }
    }
 
    // Otherwise
    return 0;
}
 
function count(a, c)
{
    count = 0;
    for(var i = 0; i < a.length; i++)
          if(a[i] == c)
            count++; 
    return count;  
}
 
function swap(s1, index1, s2, index2)
{
      var c = s1[index1];
    s1[index1] = s2[index2];
    s2[index2] = c;
}
 
var A = "adsfd";
var B = "dffff";
var M = A.length;
var N = B.length;
 
document.write(minSteps(A, B, M, N));
 
// This code is contributed by SoumikMondal
</script>
Producción: 

1

 

Complejidad temporal: O(N)
Espacio auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por IshwarGupta 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 *