Encuentre la string lexicográfica más pequeña realizando las operaciones dadas N veces

Posted on by Rudeus Greyrat

Dada una string S de N caracteres, la tarea es encontrar la string lexicográfica más pequeña después de realizar cada una de las siguientes operaciones N veces en cualquier orden:

  • Elimine el primer carácter de S e insértelo en una pila X .
  • Retire la parte superior de la pila X y agréguela al final de otra string Y que inicialmente está vacía.

Ejemplo:

Entrada: S = “cab”
Salida: abc
Explicación: La string dada se puede obtener usando las siguientes operaciones:

  1. Realice la operación 1. Por lo tanto, S = «ab», X = «c», Y = «».
  2. Realice la operación 1. Por lo tanto, S = «b», X = «ca», Y = «».
  3. Realice la operación 2. Por lo tanto, S = «b», X = «c», Y = «a».
  4. Realice la operación 1. Por lo tanto, S = «», X = «cb», Y = «a».
  5. Realice la operación 2. Por lo tanto, S = “”, X = “c”, Y = “ab”.
  6. Realice la operación 2. Por lo tanto, S = “”, X = “”, Y = “abc”.

Ahora, cada una de las operaciones dadas se realiza N veces y la string obtenida es «abc», que es la más pequeña posible.

Entrada: S = “acdb”
Salida: abdc

 

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es realizar la primera operación hasta que la parte superior de la pila contenga el carácter más pequeño después del cual se puede agregar a la string Y . Esto se puede hacer de manera eficiente manteniendo una array de sufijos, donde sufijo[i] almacena el valor ASCII más pequeño del sufijo hasta el i -ésimo carácter. A continuación se detallan los pasos a seguir:

  • Recorra la string y cree una array de sufijos suff[] según sea necesario.
  • Si la pila X no está vacía y suff[i] es mayor que el carácter superior de la pila X , extraiga el carácter superior de la pila X y agréguelo a la string Y.
  • De lo contrario, si suff[i] es igual a S[i], agregue a la string Y .
  • De lo contrario, inserte el carácter S[i] en la pila X .

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

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find lexicographical smallest
// string by performing the given operations
string smallestString(string S)
{
    // Stores the size of S
    int N = S.size();
 
    // Suffix Array
    int suff[N + 1];
 
    // Initial Condition
    suff[N] = INT_MAX;
 
    // Loop to calculate suffix array
    for (int i = N - 1; i >= 0; i--) {
        suff[i] = min(suff[i + 1], (int)S[i]);
    }
 
    // Initialize the stack X
    // and string y as empty
    stack<char> X;
    string Y = "";
 
    // Loop to traverse string
    for (int i = 0; i < N; i++) {
        // If X is not empty and suff[i]
        // is  greater than equal to top
        // character of stack X
        if (X.size() > 0 && suff[i] >= X.top()) {
            Y += X.top();
            X.pop();
            i--;
        }
 
        // If suff[i] is equal to S[i]
        else if (suff[i] == S[i]) {
            Y += S[i];
        }
 
        // Otherwise push character
        // S[i] into the stack X
        else {
            X.push(S[i]);
        }
    }
 
    // Append all remaining characters
    // of X into string Y
    while (X.size() > 0) {
        Y += X.top();
        X.pop();
    }
 
    // Return Answer
    return Y;
}
 
// Driver Code
int main()
{
    string s = "acdb";
    cout << smallestString(s);
    return 0;
}

Java

// Java program of the above approach
import java.util.*;
class GFG
{
 
  // Function to find lexicographical smallest
  // string by performing the given operations
  public static String smallestString(String S)
  {
 
    // Stores the size of S
    int N = S.length();
 
    // Suffix Array
    int[] suff = new int[N + 1];
 
    // Initial Condition
    suff[N] = Integer.MAX_VALUE;
 
    // Loop to calculate suffix array
    for (int i = N - 1; i >= 0; i--) {
      suff[i]
        = Math.min(suff[i + 1], (int)S.charAt(i));
    }
 
    // Initialize the stack X
    // and string y as empty
    Stack<Character> X = new Stack<Character>();
    String Y = "";
 
    // Loop to traverse string
    for (int i = 0; i < N; i++)
    {
 
      // If X is not empty and suff[i]
      // is  greater than equal to top
      // character of stack X
      if (X.size() > 0 && suff[i] >= X.peek()) {
        Y += X.peek();
        X.pop();
        i--;
      }
 
      // If suff[i] is equal to S[i]
      else if (suff[i] == S.charAt(i)) {
        Y += S.charAt(i);
      }
 
      // Otherwise push character
      // S[i] into the stack X
      else {
        X.push(S.charAt(i));
      }
    }
 
    // Append all remaining characters
    // of X into string Y
    while (X.size() > 0) {
      Y += X.peek();
      X.pop();
    }
 
    // Return Answer
    return Y;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String s = "acdb";
    System.out.print(smallestString(s));
  }
}
 
// This code is contributed by Taranpreet

Python3

# Python program of the above approach
import sys
 
# Function to find lexicographical smallest
# string by performing the given operations
def smallestString(S):
 
    # Stores the size of S
    N = len(S)
 
    # Suffix Array
    suff = [0]*(N+1)
 
    # Initial Condition
    suff[N] = sys.maxsize
 
    # Loop to calculate suffix array
    for i in range(N - 1, -2, -1):
        suff[i] = min(suff[i + 1], ord(S[i]))
 
    # Initialize the stack X
    # and string y as empty
    X = []
 
    Y = ""
 
    # Loop to traverse string
    for i in range(0, N):
       
        # If X is not empty and suff[i]
        # is  greater than equal to top
        # character of stack X
        if (len(X) > 0 and suff[i] >= ord(X[-1])):
            Y = Y + X[-1]
            X.pop()
            i = i - 1
 
        # If suff[i] is equal to S[i]
        elif (suff[i] == ord(S[i])):
            Y = Y + S[i]
 
        # Otherwise push character
        # S[i] into the stack X
        else:
            X.append(S[i])
 
    # Append all remaining characters
    # of X into string Y
    while (len(X) > 0):
        Y = Y + X[-1]
        X.pop()
 
    # Return Answer
    return Y
 
# Driver Code
s = "acdb"
print(smallestString(s))
 
# This code is contributed by Taranpreet

C#

// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to find lexicographical smallest
  // string by performing the given operations
  public static String smallestString(String S)
  {
 
    // Stores the size of S
    int N = S.Length;
 
    // Suffix Array
    int[] suff = new int[N + 1];
 
    // Initial Condition
    suff[N] = int.MaxValue;
 
    // Loop to calculate suffix array
    for (int i = N - 1; i >= 0; i--)
    {
      suff[i]
        = Math.Min(suff[i + 1], (int)S[i]);
    }
 
    // Initialize the stack X
    // and string y as empty
    Stack<char> X = new Stack<char>();
    String Y = "";
 
    // Loop to traverse string
    for (int i = 0; i < N; i++)
    {
 
      // If X is not empty and suff[i]
      // is  greater than equal to top
      // character of stack X
      if (X.Count > 0 && suff[i] >= X.Peek())
      {
        Y += X.Peek();
        X.Pop();
        i--;
      }
 
      // If suff[i] is equal to S[i]
      else if (suff[i] == S[i])
      {
        Y += S[i];
      }
 
      // Otherwise push character
      // S[i] into the stack X
      else
      {
        X.Push(S[i]);
      }
    }
 
    // Append all remaining characters
    // of X into string Y
    while (X.Count > 0)
    {
      Y += X.Peek();
      X.Pop();
    }
 
    // Return Answer
    return Y;
  }
 
  // Driver Code
  public static void Main()
  {
    String s = "acdb";
    Console.Write(smallestString(s));
  }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to find lexicographical smallest
       // string by performing the given operations
       function smallestString(S) {
           // Stores the size of S
           let N = S.length;
 
           // Suffix Array
           let suff = new Array(N + 1);
 
           // Initial Condition
           suff[N] = Number.MAX_VALUE;
 
           // Loop to calculate suffix array
           for (let i = N - 1; i >= 0; i--) {
               suff[i] = Math.min(suff[i + 1], S[i].charCodeAt(0));
           }
 
           // Initialize the stack X
           // and string y as empty
           let X = [];
           let Y = "";
 
           // Loop to traverse string
           for (let i = 0; i < N; i++) {
               // If X is not empty and suff[i]
               // is  greater than equal to top
               // character of stack X
               if (X.length > 0 && suff[i] >= X[X.length - 1].charCodeAt(0)) {
                   Y += X[X.length - 1];
                   X.pop();
                   i--;
               }
 
               // If suff[i] is equal to S[i]
               else if (String.fromCharCode(suff[i]) == S[i]) {
                   Y += S[i];
               }
 
               // Otherwise push character
               // S[i] into the stack X
               else {
                   X.push(S[i]);
               }
           }
 
           // Append all remaining characters
           // of X into string Y
           while (X.length > 0) {
               Y += X[X.length - 1];
               X.pop();
           }
 
           // Return Answer
           return Y;
       }
 
       // Driver Code
 
       let s = "acdb";
       document.write(smallestString(s));
 
      // This code is contributed by Potta Lokesh
   </script>
Producción

abdc

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

Publicación traducida automáticamente

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