Dada una string S , la tarea es encontrar la subsecuencia lexicográficamente más grande que se puede formar usando todos los caracteres distintos solo una vez de la string dada.
Ejemplos:
Entrada: S = ababc
Salida: bac
Explicación:
Todas las subsecuencias posibles que contienen todos los caracteres en S exactamente una vez son {“abc”, “bac”}. El máximo lexicográficamente entre todas las subsecuencias es “bac”.Entrada: S = “zydsbacab”
Salida: zydscab
Enfoque: El problema dado se puede resolver usando Stack . La idea es atravesar la string y almacenar esos caracteres en la pila en orden lexicográficamente mayor para generar la string resultante. Siga los pasos a continuación para resolver el problema dado:
- Almacene la frecuencia de todos los caracteres de la string S en una array , digamos count[] .
- Inicialice una array , digamos visited[] , que almacene si algún carácter está presente en la pila o no.
- Recorra la string S dada usando la variable i y realice los siguientes pasos:
- Disminuya la frecuencia del carácter S[i] en la array count[] en 1 .
- Ahora, si el personaje ya está presente en la pila, continúe con la siguiente iteración .
- De lo contrario, verifique si el carácter actual es mayor que el carácter superior en la pila y la frecuencia del carácter superior es mayor que 0 , luego siga extrayendo el elemento superior de la pila .
- Después de los pasos anteriores, agregue el carácter actual y márquelo como visitado en la array visited[] .
- Después de completar los pasos anteriores, genere la string utilizando los caracteres de la pila e imprima el reverso para obtener la subsecuencia lexicográficamente más grande .
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 lexicographically
// largest subsequence consisting of all
// distinct characters of S only once
string lexicoMaxSubsequence(string s, int n)
{
stack<char> st;
// Stores if any alphabet is present
// in the current stack
vector<int> visited(26, 0), cnt(26, 0);
// Findthe number of occurrences of
// the character s[i]
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']++;
}
for (int i = 0; i < n; i++) {
// Decrease the character count
// in remaining string
cnt[s[i] - 'a']--;
// If character is already present
// in the stack
if (visited[s[i] - 'a']) {
continue;
}
// if current character is greater
// than last character in stack
// then pop the top character
while (!st.empty() && st.top() < s[i]
&& cnt[st.top() - 'a'] != 0) {
visited[st.top() - 'a'] = 0;
st.pop();
}
// Push the current character
st.push(s[i]);
visited[s[i] - 'a'] = 1;
}
// Stores the resultant string
string s1;
// Generate the string
while (!st.empty()) {
s1 = st.top() + s1;
st.pop();
}
// Return the resultant string
return s1;
}
// Driver Code
int main()
{
string S = "ababc";
int N = S.length();
cout << lexicoMaxSubsequence(S, N);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Function to find the lexicographically
// largest subsequence consisting of all
// distinct characters of S only once
static String lexicoMaxSubsequence(String s, int n)
{
Stack<Character> st = new Stack<Character>();
// Stores if any alphabet is present
// in the current stack
int[] visited = new int[26];
int[] cnt = new int[26];
for (int i = 0; i < 26; i++) {
visited[i] = 0;
cnt[i] = 0;
}
// Findthe number of occurrences of
// the character s[i]
for (int i = 0; i < n; i++) {
cnt[s.charAt(i) - 'a']++;
}
for (int i = 0; i < n; i++) {
// Decrease the character count
// in remaining string
cnt[s.charAt(i) - 'a']--;
// If character is already present
// in the stack
if (visited[s.charAt(i) - 'a'] > 0) {
continue;
}
// if current character is greater
// than last character in stack
// then pop the top character
while (!st.empty() && st.peek() < s.charAt(i)
&& cnt[st.peek() - 'a'] != 0) {
visited[st.peek() - 'a'] = 0;
st.pop();
}
// Push the current character
st.push(s.charAt(i));
visited[s.charAt(i) - 'a'] = 1;
}
// Stores the resultant string
String s1 = "";
// Generate the string
while (!st.empty()) {
s1 = st.peek() + s1;
st.pop();
}
// Return the resultant string
return s1;
}
// Driver Code
public static void main(String[] args)
{
String S = "ababc";
int N = S.length();
System.out.println(lexicoMaxSubsequence(S, N));
}
}
// This code is contributed by maddler.
Python3
# Python3 program for the above approach
# Function to find the lexicographically
# largest subsequence consisting of all
# distinct characters of S only once
def lexicoMaxSubsequence(s, n):
st = []
# Stores if any alphabet is present
# in the current stack
visited = [0]*(26)
cnt = [0]*(26)
for i in range(26):
visited[i] = 0
cnt[i] = 0
# Findthe number of occurrences of
# the character s[i]
for i in range(n):
cnt[ord(s[i]) - ord('a')]+=1
for i in range(n):
# Decrease the character count
# in remaining string
cnt[ord(s[i]) - ord('a')]-=1
# If character is already present
# in the stack
if (visited[ord(s[i]) - ord('a')] > 0):
continue
# if current character is greater
# than last character in stack
# then pop the top character
while (len(st) > 0 and ord(st[-1]) < ord(s[i]) and cnt[ord(st[-1]) - ord('a')] != 0):
visited[ord(st[-1]) - ord('a')] = 0
st.pop()
# Push the current character
st.append(s[i])
visited[ord(s[i]) - ord('a')] = 1
# Stores the resultant string
s1 = ""
# Generate the string
while (len(st) > 0):
s1 = st[-1] + s1
st.pop()
# Return the resultant string
return s1
S = "ababc"
N = len(S)
print(lexicoMaxSubsequence(S, N))
# This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the lexicographically
// largest subsequence consisting of all
// distinct characters of S only once
static string lexicoMaxSubsequence(string s, int n)
{
Stack<char> st = new Stack<char>();
// Stores if any alphabet is present
// in the current stack
int[] visited = new int[26];
int[] cnt = new int[26];
for (int i = 0; i < 26; i++) {
visited[i] = 0;
cnt[i] = 0;
}
// Findthe number of occurrences of
// the character s[i]
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']++;
}
for (int i = 0; i < n; i++) {
// Decrease the character count
// in remaining string
cnt[s[i] - 'a']--;
// If character is already present
// in the stack
if (visited[s[i] - 'a'] > 0) {
continue;
}
// if current character is greater
// than last character in stack
// then pop the top character
while (st.Count > 0 && st.Peek() < s[i]
&& cnt[st.Peek() - 'a'] != 0) {
visited[st.Peek() - 'a'] = 0;
st.Pop();
}
// Push the current character
st.Push(s[i]);
visited[s[i] - 'a'] = 1;
}
// Stores the resultant string
string s1 = "";
// Generate the string
while (st.Count > 0) {
s1 = st.Peek() + s1;
st.Pop();
}
// Return the resultant string
return s1;
}
static void Main() {
string S = "ababc";
int N = S.Length;
Console.Write(lexicoMaxSubsequence(S, N));
}
}
// This code is contributed by suresh07.
Javascript
<script>
// Javascript program for the above approach
// Function to find the lexicographically
// largest subsequence consisting of all
// distinct characters of S only once
function lexicoMaxSubsequence(s, n)
{
let st = [];
// Stores if any alphabet is present
// in the current stack
let visited = new Array(26);
let cnt = new Array(26);
for (let i = 0; i < 26; i++) {
visited[i] = 0;
cnt[i] = 0;
}
// Findthe number of occurrences of
// the character s[i]
for (let i = 0; i < n; i++) {
cnt[s[i].charCodeAt() - 'a'.charCodeAt()]++;
}
for (let i = 0; i < n; i++) {
// Decrease the character count
// in remaining string
cnt[s[i].charCodeAt() - 'a'.charCodeAt()]--;
// If character is already present
// in the stack
if (visited[s[i].charCodeAt() - 'a'.charCodeAt()] > 0) {
continue;
}
// if current character is greater
// than last character in stack
// then pop the top character
while (st.length > 0 && st[st.length - 1].charCodeAt() < s[i].charCodeAt()
&& cnt[st[st.length - 1].charCodeAt() - 'a'.charCodeAt()] != 0) {
visited[st[st.length - 1].charCodeAt() - 'a'.charCodeAt()] = 0;
st.pop();
}
// Push the current character
st.push(s[i]);
visited[s[i].charCodeAt() - 'a'.charCodeAt()] = 1;
}
// Stores the resultant string
let s1 = "";
// Generate the string
while (st.length > 0) {
s1 = st[st.length - 1] + s1;
st.pop();
}
// Return the resultant string
return s1;
}
let S = "ababc";
let N = S.length;
document.write(lexicoMaxSubsequence(S, N));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
bac
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dinijain99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA