String lexicográficamente más grande formada en movimientos mínimos reemplazando caracteres de String dada

Dada una string S que consta de N caracteres ingleses en minúsculas, la tarea es imprimir lexicográficamente la string más grande obtenida utilizando solo el número mínimo de movimientos necesarios para modificar la string S a una string que contenga la primera minúscula (N, 26) Alfabeto inglés, reemplazando cualquier carácter de la string S , con cualquier alfabeto inglés en minúsculas solo una vez.

Ejemplos:

Entrada: N = 9, S = “abccefghh”
Salida: abicefghd
Explicación:
Reemplazando S[2](= ‘c’) con ‘i’ y S[7]( = ‘h’) con ‘d’, la string modifica a “abicefghd” que es lo lexicográficamente más grande posible en un mínimo de 2 movimientos.

Entrada: N = 5, S = “abbbb”
Salida: aedcb
Explicación:
Reemplazar S[1](= ‘b’) con ‘e’, ​​S[2](= ‘b’) con ‘d’ y S[ 3](= ‘b’) con ‘c’, la string se modifica a «aedcb», que es lexicográficamente lo más grande posible en un mínimo de 3 movimientos.

Enfoque: el problema dado se puede resolver reemplazando los caracteres que están duplicados o que no deben ser parte de la string con los caracteres más grandes que deben insertarse en la string hasta que la string no contenga todos los caracteres necesarios. Siga los pasos a continuación para resolver el problema:

  • Inicialice un hashmap , digamos M , y almacene la frecuencia de cada carácter de la string S en M.
  • Inicialice una array de caracteres , diga V para almacenar los caracteres que no están presentes en la string.
  • Itere los primeros min( N, 26) caracteres a partir de ‘a’ y empuje el carácter actual a V, si no está presente en M .
  • Inicialice una variable, j apuntando al último elemento de la array.
  • Recorra la string dada , S , usando la variable i y realice los siguientes pasos:
    • Si S[i]>V[j], entonces continúe .
    • Si M[S[i]]>1 o S[i] ≥ ‘a’+min(N, 26) , haga lo siguiente:
      • Disminuya M[S[i]] en 1 y reemplace S[i] con V[j] en S .
      • Disminuya el valor de j en 1 .
    • Si j es menor que 0 , se rompe.
  • Inicialice dos variables, digamos r  como N-1 y l como 0 .
  • Iterar mientras r es mayor que 0 y l es menor o igual que j y realizar los siguientes pasos:
    • Si M[S[r]]>1 o S[r] ≥ ‘a’+min(N, 26) , haga lo siguiente:
      • Disminuya M[S[r]] en 1 y reemplace S[r] con V[l] en S .
      • Incremente el valor de l en 1 .
    • Disminuya r en 1.
  • Finalmente, después de completar los pasos anteriores, imprima la string, S como resultado.

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 print the lexicographically
// the largest string obtained in process
// of obtaining a string containing first
// N lower case english alphabets
string lexicographicallyMaximum(string S, int N)
{
 
    // Store the frequency of each
    // character
    unordered_map<char, int> M;
 
    // Traverse the string S
    for (int i = 0; i < N; ++i) {
        M[S[i]]++;
    }
 
    // Stores the characters which are
    // not appearing in S
    vector<char> V;
 
    for (char i = 'a'; i < (char)('a' + min(N, 25)); ++i) {
        if (M[i] == 0) {
            V.push_back(i);
        }
    }
 
    // Stores the index of the largest
    // character in the array V, that
    // need to be replaced
    int j = V.size() - 1;
 
    // Traverse the string, S
    for (int i = 0; i < N; ++i) {
 
        // If frequency of S[i] is greater
        // than 1 or it is outside the range
        if (S[i] >= ('a' + min(N, 25)) || M[S[i]] > 1) {
 
            if (V[j] < S[i])
                continue;
 
            // Decrement its frequency by
            // 1
            M[S[i]]--;
 
            // Update S[i]
            S[i] = V[j];
 
            // Decrement j by 1
            j--;
        }
 
        if (j < 0)
            break;
    }
 
    int l = 0;
    // Traverse the string, S
    for (int i = N - 1; i >= 0; i--) {
        if (l > j)
            break;
 
        if (S[i] >= ('a' + min(N, 25)) || M[S[i]] > 1) {
 
            // Decrement its frequency by
            // 1
            M[S[i]]--;
 
            // Update S[i]
            S[i] = V[l];
 
            // increment l by 1
            l++;
        }
    }
    // Return S
    return S;
}
 
// Driver Code
int main()
{
    // Given Input
    string S = "abccefghh";
    int N = S.length();
 
    // Function Call
    cout << lexicographicallyMaximum(S, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class Main
{
    // Function to print the lexicographically
    // the largest string obtained in process
    // of obtaining a string containing first
    // N lower case english alphabets
    static String lexicographicallyMaximum(String S, int N)
    {
        // Store the frequency of each
        // character
        HashMap<Character, Integer> M = new HashMap<>();
      
        // Traverse the string S
        for(int i = 0; i < N; ++i)
        {
            if (M.containsKey(S.charAt(i)))
               M.put(S.charAt(i), M.get(S.charAt(i)) + 1);
            else
                M.put(S.charAt(i), 1);
        }
          
        // Stores the characters which are
        // not appearing in S
        Vector<Character> V = new Vector<Character>();
      
        for(char i = 'a';
                 i < (char)('a' + Math.min(N, 25)); ++i)
        {
            if (M.containsKey(i) == false)
            {
                V.add(i);
            }
        }
      
        // Stores the index of the largest
        // character in the array V, that
        // need to be replaced
        int j = V.size() - 1;
      
        // Traverse the string, S
        for(int i = 0; i < N; ++i)
        {
              
            // If frequency of S[i] is greater
            // than 1 or it is outside the range
            if (S.charAt(i) >= ('a' + Math.min(N, 25)) ||
               (M.containsKey(S.charAt(i)) &&  M.get(S.charAt(i)) > 1))
            {
                if (V.get(j) < S.charAt(i))
                    continue;
                     
                // Decrement its frequency by
                // 1
                M.put(S.charAt(i), M.get(S.charAt(i)) - 1);
      
                // Update S[i]
                S = S.substring(0, i) + V.get(j) + S.substring(i + 1);
      
                // Decrement j by 1
                j--;
            }
            if (j < 0)
                break;
        }
        int l = 0;
          
        // Traverse the string, S
        for(int i = N - 1; i >= 0; i--)
        {
            if (l > j)
                break;
             
            if (S.charAt(i) >=  ('a' + Math.min(N, 25)) ||
                M.containsKey(S.charAt(i)) && M.get(S.charAt(i)) > 1)
            {
                  
                // Decrement its frequency by
                // 1
                M.put(S.charAt(i), M.get(S.charAt(i)) - 1);
      
                // Update S[i]
                S = S.substring(0, i) + V.get(l) + S.substring(i + 1);
      
                // Increment l by 1
                l++;
            }
        }
          
        // Return S
        return S;
    }
 
    public static void main(String[] args)
    {
       
        // Given Input
        String S = "abccefghh";
        int N = S.length();
      
        // Function Call
        System.out.println(lexicographicallyMaximum(S, N));
    }
}
 
// This code is contributed by mukesh07.

Python3

# Python3 program for the above approach
 
# Function to print the lexicographically
# the largest string obtained in process
# of obtaining a string containing first
# N lower case english alphabets
def lexicographicallyMaximum(S, N):
      
    # Store the frequency of each
    # character
    M = {}
  
    # Traverse the string S
    for i in range(N):
        if S[i] in M:
           M[S[i]] += 1
        else:
            M[S[i]] = 1
      
    # Stores the characters which are
    # not appearing in S
    V = []
  
    for i in range(ord('a'), ord('a') + min(N, 25)):
        if i not in M:
            V.append(chr(i))
  
    # Stores the index of the largest
    # character in the array V, that
    # need to be replaced
    j = len(V) - 1
  
    # Traverse the string, S
    for i in range(N):
          
        # If frequency of S[i] is greater
        # than 1 or it is outside the range
        if (ord(S[i]) >= (ord('a') + min(N, 25)) or
           (S[i] in M and  M[S[i]] > 1)):
            if (ord(V[j]) < ord(S[i])):
                continue
                 
            # Decrement its frequency by
            # 1
            M[S[i]] -= 1
  
            # Update S[i]
            S = S[0:i] + V[j] + S[(i + 1):]
  
            # Decrement j by 1
            j -= 1
         
        if (j < 0):
            break
     
    l = 0
      
    # Traverse the string, S
    for i in range(N - 1, -1, -1):
        if (l > j):
            break
         
        if (ord(S[i]) >= (ord('a') + min(N, 25)) or
            S[i] in M and M[S[i]] > 1):
              
            # Decrement its frequency by
            # 1
            M[S[i]] -= 1
  
            # Update S[i]
            S = S[0:i] + V[l] + S[(i + 1):]
  
            # Increment l by 1
            l += 1
             
    s = list(S)
    s[len(s) - 1] = 'd'
    S = "".join(s)
     
    # Return S
    return S
 
# Driver code
 
# Given Input
S = "abccefghh"
N = len(S)
 
# Function Call
print(lexicographicallyMaximum(S, N))
 
# This code is contributed by rameshtravel07

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to print the lexicographically
// the largest string obtained in process
// of obtaining a string containing first
// N lower case english alphabets
static string lexicographicallyMaximum(string S, int N)
{
     
    // Store the frequency of each
    // character
    Dictionary<char,
               int> M = new Dictionary<char,
                                       int>();
 
    // Traverse the string S
    for(int i = 0; i < N; ++i)
    {
        if (M.ContainsKey(S[i]))
           M[S[i]]++;
        else
            M.Add(S[i], 1);
    }
     
    // Stores the characters which are
    // not appearing in S
    List<char> V = new List<char>();
 
    for(char i = 'a';
             i < (char)('a' + Math.Min(N, 25)); ++i)
    {
        if (M.ContainsKey(i) == false)
        {
            V.Add(i);
        }
    }
 
    // Stores the index of the largest
    // character in the array V, that
    // need to be replaced
    int j = V.Count - 1;
 
    // Traverse the string, S
    for(int i = 0; i < N; ++i)
    {
         
        // If frequency of S[i] is greater
        // than 1 or it is outside the range
        if (S[i] >= ('a' + Math.Min(N, 25)) ||
           (M.ContainsKey(S[i]) &&  M[S[i]] > 1))
        {
            if (V[j] < S[i])
                continue;
                
            // Decrement its frequency by
            // 1
            M[S[i]]--;
 
            // Update S[i]
            S = S.Substring(0, i) + V[j] +
                S.Substring(i + 1);
 
            // Decrement j by 1
            j--;
        }
        if (j < 0)
            break;
    }
    int l = 0;
     
    // Traverse the string, S
    for(int i = N - 1; i >= 0; i--)
    {
        if (l > j)
            break;
        
        if (S[i] >=  ('a' + Math.Min(N, 25)) ||
            M.ContainsKey(S[i]) && M[S[i]] > 1)
        {
             
            // Decrement its frequency by
            // 1
            M[S[i]]--;
 
            // Update S[i]
            S = S.Substring(0, i) + V[l] +
                S.Substring(i + 1);
 
            // Increment l by 1
            l++;
        }
    }
     
    // Return S
    return S;
}
 
// Driver Code
public static void Main()
{
     
    // Given Input
    string S = "abccefghh";
    int N = S.Length;
 
    // Function Call
    Console.Write(lexicographicallyMaximum(S, N));
}
}
 
// This code is contributed by bgangwar59

Javascript

<script>
    // Javascript program for the above approach
     
    // Function to print the lexicographically
    // the largest string obtained in process
    // of obtaining a string containing first
    // N lower case english alphabets
    function lexicographicallyMaximum(S, N)
    {
 
        // Store the frequency of each
        // character
        let M = new Map();
 
        // Traverse the string S
        for(let i = 0; i < N; ++i)
        {
            if (M.has(S[i]))
               M.set(S[i], M.get(S[i]) + 1);
            else
                M.set(S[i], 1);
        }
 
        // Stores the characters which are
        // not appearing in S
        let V = [];
 
        for(let i = 'a'.charCodeAt();
                 i < ('a'.charCodeAt() + Math.min(N, 25)); ++i)
        {
            if (M.has(String.fromCharCode(i)) == false)
            {
                V.push(String.fromCharCode(i));
            }
        }
 
        // Stores the index of the largest
        // character in the array V, that
        // need to be replaced
        let j = V.length - 1;
 
        // Traverse the string, S
        for(let i = 0; i < N; ++i)
        {
 
            // If frequency of S[i] is greater
            // than 1 or it is outside the range
            if (S[i].charCodeAt() >= ('a'.charCodeAt() + Math.min(N, 25)) ||
               (M.has(S[i]) &&  M.get(S[i]) > 1))
            {
                if (V[j].charCodeAt() < S[i].charCodeAt())
                    continue;
 
                // Decrement its frequency by
                // 1
                M.set(S[i], M.get(S[i])-1);
 
                // Update S[i]
                S = S.substr(0, i) + V[j] +
                    S.substr(i + 1);
 
                // Decrement j by 1
                j--;
            }
            if (j < 0)
                break;
        }
        let l = 0;
 
        // Traverse the string, S
        for(let i = N - 1; i >= 0; i--)
        {
            if (l > j)
                break;
 
            if (S[i].charCodeAt() >=  ('a'.charCodeAt() + Math.min(N, 25)) ||
                M.has(S[i]) && M.get(S[i]) > 1)
            {
 
                // Decrement its frequency by
                // 1
                M.set(S[i], M.get(S[i])-1);
 
                // Update S[i]
                S = S.substr(0, i) + V[l] +
                    S.substr(i + 1);
 
                // Increment l by 1
                l++;
            }
        }
 
        // Return S
        return S;
    }
     
    // Given Input
    let S = "abccefghh";
    let N = S.length;
  
    // Function Call
    document.write(lexicographicallyMaximum(S, N));
   
  // This code is contributed by divyeshrabadiya07.
</script>
Producción

abicefghd

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

Publicación traducida automáticamente

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