Dada una string S que consta de alfabetos en minúsculas, la tarea es encontrar la string lexicográficamente más pequeña que se pueda obtener eliminando los duplicados de la string S dada .
Ejemplos:
Entrada: S = “yzxyz”
Salida: xyz
Explicación: Eliminando los caracteres duplicados en los índices 0 y 1 en la string dada, la string restante “xyz” consta solo de alfabetos únicos y es la string más pequeña posible en orden lexicográfico.Entrada: S = “acbc”
Salida: “abc”
Explicación: Eliminando los caracteres duplicados en el índice 3 en la string dada, la string restante “abc” consta solo de alfabetos únicos y es la string más pequeña posible en orden lexicográfico.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una string res para almacenar la string resultante.
- Almacene la frecuencia de cada carácter presente en la string dada en una array freq[] .
- Mantenga una array vis[] para marcar los caracteres que ya están presentes en la string resultante res .
- Recorra la string S dada y para cada carácter S[i] , realice lo siguiente:
- Disminuye la frecuencia del carácter actual en 1 .
- Si el carácter actual no está marcado como visitado en la array vis[] , realice lo siguiente:
- Si la última letra de res es menor que S[i] , agregue S[i] a res .
- Si la última letra de res es mayor que S[i] y el recuento de la última letra de res supera 0 , elimine ese carácter y marque visit[S[i]] como 0 y continúe con este paso hasta que se cumpla la condición anterior. .
- Después de salir de la condición anterior, agregue S[i] a res y marque visit[S[i]] como 1 .
- Después de completar los pasos anteriores, imprima la string res 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 that finds lexicographically
// smallest string after removing the
// duplicates from the given string
string removeDuplicateLetters(string s)
{
// Stores the frequency of characters
int cnt[26] = { 0 };
// Mark visited characters
int vis[26] = { 0 };
int n = s.size();
// Stores count of each character
for (int i = 0; i < n; i++)
cnt[s[i] - 'a']++;
// Stores the resultant string
string res = "";
for (int i = 0; i < n; i++) {
// Decrease the count of
// current character
cnt[s[i] - 'a']--;
// If character is not already
// in answer
if (!vis[s[i] - 'a']) {
// Last character > S[i]
// and its count > 0
while (res.size() > 0
&& res.back() > s[i]
&& cnt[res.back() - 'a'] > 0) {
// Mark letter unvisited
vis[res.back() - 'a'] = 0;
res.pop_back();
}
// Add s[i] in res and
// mark it visited
res += s[i];
vis[s[i] - 'a'] = 1;
}
}
// Return the resultant string
return res;
}
// Driver Code
int main()
{
// Given string S
string S = "acbc";
// Function Call
cout << removeDuplicateLetters(S);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function that finds lexicographically
// smallest string after removing the
// duplicates from the given string
static String removeDuplicateLetters(String s)
{
// Stores the frequency of characters
int[] cnt = new int[26];
// Mark visited characters
int[] vis = new int[26];
int n = s.length();
// Stores count of each character
for(int i = 0; i < n; i++)
cnt[s.charAt(i) - 'a']++;
// Stores the resultant string
String res = "";
for(int i = 0; i < n; i++)
{
// Decrease the count of
// current character
cnt[s.charAt(i) - 'a']--;
// If character is not already
// in answer
if (vis[s.charAt(i) - 'a'] == 0)
{
// Last character > S[i]
// and its count > 0
int size = res.length();
while (size > 0 &&
res.charAt(size - 1) > s.charAt(i) &&
cnt[res.charAt(size - 1) - 'a'] > 0)
{
// Mark letter unvisited
vis[res.charAt(size - 1) - 'a'] = 0;
res = res.substring(0, size - 1);
size--;
}
// Add s[i] in res and
// mark it visited
res += s.charAt(i);
vis[s.charAt(i) - 'a'] = 1;
}
}
// Return the resultant string
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given string S
String S = "acbc";
// Function Call
System.out.println(removeDuplicateLetters(S));
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach
# Function that finds lexicographically
# smallest after removing the
# duplicates from the given string
def removeDuplicateLetters(s):
# Stores the frequency of characters
cnt = [0] * 26
# Mark visited characters
vis = [0] * 26
n = len(s)
# Stores count of each character
for i in s:
cnt[ord(i) - ord('a')] += 1
# Stores the resultant string
res = []
for i in range(n):
# Decrease the count of
# current character
cnt[ord(s[i]) - ord('a')] -= 1
# If character is not already
# in answer
if (not vis[ord(s[i]) - ord('a')]):
# Last character > S[i]
# and its count > 0
while (len(res) > 0 and
res[-1] > s[i] and
cnt[ord(res[-1]) - ord('a')] > 0):
# Mark letter unvisited
vis[ord(res[-1]) - ord('a')] = 0
del res[-1]
# Add s[i] in res and
# mark it visited
res += s[i]
vis[ord(s[i]) - ord('a')] = 1
# Return the resultant string
return "".join(res)
# Driver Code
if __name__ == '__main__':
# Given S
S = "acbc"
# Function Call
print(removeDuplicateLetters(S))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function that finds lexicographically
// smallest string after removing the
// duplicates from the given string
static string removeDuplicateLetters(string s)
{
// Stores the frequency of characters
int[] cnt = new int[26];
// Mark visited characters
int[] vis = new int[26];
int n = s.Length;
// Stores count of each character
for(int i = 0; i < n; i++)
cnt[s[i] - 'a']++;
// Stores the resultant string
String res = "";
for(int i = 0; i < n; i++)
{
// Decrease the count of
// current character
cnt[s[i] - 'a']--;
// If character is not already
// in answer
if (vis[s[i] - 'a'] == 0)
{
// Last character > S[i]
// and its count > 0
int size = res.Length;
while (size > 0 && res[size - 1] > s[i] &&
cnt[res[size - 1] - 'a'] > 0)
{
// Mark letter unvisited
vis[res[size - 1] - 'a'] = 0;
res = res.Substring(0, size - 1);
size--;
}
// Add s[i] in res and
// mark it visited
res += s[i];
vis[s[i] - 'a'] = 1;
}
}
// Return the resultant string
return res;
}
// Driver Code
public static void Main()
{
// Given string S
string S = "acbc";
// Function Call
Console.WriteLine(removeDuplicateLetters(S));
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program for the above approach
// Function that finds lexicographically
// smallest string after removing the
// duplicates from the given string
function removeDuplicateLetters(s)
{
// Stores the frequency of characters
var cnt = Array(26).fill(0);
// Mark visited characters
var vis = Array(26).fill(false);
var n = s.length;
// Stores count of each character
for (var i = 0; i < n; i++)
cnt[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// Stores the resultant string
var res = "";
for (var i = 0; i < n; i++) {
// Decrease the count of
// current character
cnt[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]--;
// If character is not already
// in answer
if (!vis[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]) {
// Last character > S[i]
// and its count > 0
while (res.length > 0
&& res[res.length-1].charCodeAt(0) >
s[i].charCodeAt(0)
&& cnt[res[res.length-1].charCodeAt(0) -
'a'.charCodeAt(0)] > 0) {
// Mark letter unvisited
vis[res[res.length-1].charCodeAt(0) -
'a'.charCodeAt(0)] = 0;
res = res.substring(0, res.length-1);
}
// Add s[i] in res and
// mark it visited
res += s[i];
vis[s[i].charCodeAt(0) - 'a'.charCodeAt(0)] = 1;
}
}
// Return the resultant string
return res;
}
// Driver Code
// Given string S
var S = "acbc";
// Function Call
document.write( removeDuplicateLetters(S));
</script>
Producción:
abc
Complejidad de tiempo: O(N)
Espacio auxiliar: O(1) (ya que estamos usando la array visited y cnt de tamaño fijo 26)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA