Dada una string str , que consta de letras en minúsculas, la tarea es encontrar la string más corta que no sea una subsecuencia de la string dada. Si existen varias strings, imprima cualquiera de ellas.
Ejemplos:
Entrada: str = “abaabcc”
Salida: d
Explicación:
Una de las strings más cortas posibles que no es una subsecuencia de la string dada es “d”. Por lo tanto, la salida requerida es «d».Entrada: str = “abcdefghijklmnopqrstuvwxyzaabbccdd”
Salida: ze
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice una string , digamos shortestString , para almacenar la string más corta que no sea una subsecuencia de la string dada.
- Inicialice un Conjunto , digamos segmentos , para almacenar todos los caracteres posibles de cada subsegmento.
- Atraviese la string e inserte el carácter de la string en segmentos y verifique si los segmentos contienen todos los alfabetos en minúsculas o no. Si se determina que es cierto, agregue el carácter actual en shortestString y elimine todos los elementos de los segmentos .
- Repita todos los alfabetos en minúsculas posibles en el rango [a – z] y verifique si el carácter actual está presente en el segmento o no. Si se determina que es cierto, inserte el carácter actual en shortestString .
- Finalmente, imprima el valor de shortestString .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find shortest string which
// not a subsequence of the given string
string ShortestSubsequenceNotPresent(string str)
{
// Stores the shortest string which is
// not a subsequence of the given string
string shortestString;
// Stores length of string
int N = str.length();
// Stores distinct character of subsegments
unordered_set<char> subsegments;
// Traverse the given string
for (int i = 0; i < N; i++) {
// Insert current character
// into subsegments
subsegments.insert(str[i]);
// If all lowercase alphabets
// present in the subsegment
if (subsegments.size() == 26) {
// Insert the last character of
// subsegment into shortestString
shortestString.push_back(str[i]);
// Remove all elements from
// the current subsegment
subsegments.clear();
}
}
// Traverse all lowercase alphabets
for (char ch = 'a'; ch <= 'z'; ch++) {
// If current character is not
// present in the subsegment
if (subsegments.count(ch) == 0) {
shortestString.push_back(ch);
// Return shortestString
return shortestString;
}
}
return shortestString;
}
// Driver Code
int main()
{
// Given String
string str
= "abcdefghijklmnopqrstuvwxyzaabbccdd";
cout << ShortestSubsequenceNotPresent(str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
public static String
ShortestSubsequenceNotPresent(String str)
{
// Stores the shortest string which is
// not a subsequence of the given string
String shortestString = "";
// Stores length of string
int N = str.length();
// Stores distinct character of subsegments
HashSet<Character> subsegments = new HashSet<>();
// Traverse the given string
for (int i = 0; i < N; i++) {
// Insert current character
// into subsegments
subsegments.add(str.charAt(i));
// If all lowercase alphabets
// present in the subsegment
if (subsegments.size() == 26) {
// Insert the last character of
// subsegment into shortestString
shortestString
= shortestString + str.charAt(i);
// Remove all elements from
// the current subsegment
subsegments.clear();
}
}
// Traverse all lowercase alphabets
for (char ch = 'a'; ch <= 'z'; ch++) {
// If current character is not
// present in the subsegment
if (!subsegments.contains(ch)) {
shortestString = shortestString + ch;
// Return shortestString
return shortestString;
}
}
return shortestString;
}
// Driver Code
public static void main(String[] args)
{
String str = "abcdefghijklmnopqrstuvwxyzaabbccdd";
System.out.print(
ShortestSubsequenceNotPresent(str));
}
}
// This code is contributed by Manu Pathria
Python3
# Python3 program to implement # the above approach # Function to find shortest string which # not a subsequence of the given string def ShortestSubsequenceNotPresent(Str): # Stores the shortest string which is # not a subsequence of the given string shortestString = "" # Stores length of string N = len(Str) # Stores distinct character of subsegments subsegments = set() # Traverse the given string for i in range(N): # Insert current character # into subsegments subsegments.add(Str[i]) # If all lowercase alphabets # present in the subsegment if (len(subsegments) == 26) : # Insert the last character of # subsegment into shortestString shortestString += Str[i] # Remove all elements from # the current subsegment subsegments.clear() # Traverse all lowercase alphabets for ch in range(int(26)): # If current character is not # present in the subsegment if (chr(ch + 97) not in subsegments) : shortestString += chr(ch + 97) # Return shortestString return shortestString return shortestString # Driver code # Given String Str = "abcdefghijklmnopqrstuvwxyzaabbccdd" print(ShortestSubsequenceNotPresent(Str)) # This code is contributed by divyeshrabadiya07
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
public static String ShortestSubsequenceNotPresent(
String str)
{
// Stores the shortest string which is
// not a subsequence of the given string
String shortestString = "";
// Stores length of string
int N = str.Length;
// Stores distinct character of subsegments
HashSet<char> subsegments = new HashSet<char>();
// Traverse the given string
for(int i = 0; i < N; i++)
{
// Insert current character
// into subsegments
subsegments.Add(str[i]);
// If all lowercase alphabets
// present in the subsegment
if (subsegments.Count == 26)
{
// Insert the last character of
// subsegment into shortestString
shortestString = shortestString + str[i];
// Remove all elements from
// the current subsegment
subsegments.Clear();
}
}
// Traverse all lowercase alphabets
for(char ch = 'a'; ch <= 'z'; ch++)
{
// If current character is not
// present in the subsegment
if (!subsegments.Contains(ch))
{
shortestString = shortestString + ch;
// Return shortestString
return shortestString;
}
}
return shortestString;
}
// Driver Code
public static void Main(String[] args)
{
String str = "abcdefghijklmnopqrstuvwxyzaabbccdd";
Console.Write(
ShortestSubsequenceNotPresent(str));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find shortest string which
// not a subsequence of the given string
function ShortestSubsequenceNotPresent(str)
{
// Stores the shortest string which is
// not a subsequence of the given string
var shortestString = [];
// Stores length of string
var N = str.length;
// Stores distinct character of subsegments
var subsegments = new Set();
// Traverse the given string
for (var i = 0; i < N; i++) {
// Insert current character
// into subsegments
subsegments.add(str[i].charCodeAt(0));
// If all lowercase alphabets
// present in the subsegment
if (subsegments.size == 26) {
// Insert the last character of
// subsegment into shortestString
shortestString.push(str[i]);
// Remove all elements from
// the current subsegment
subsegments = new Set();
}
}
// Traverse all lowercase alphabets
for (var ch = 'a'.charCodeAt(0);
ch <= 'z'.charCodeAt(0); ch++) {
// If current character is not
// present in the subsegment
if (!subsegments.has(ch)) {
shortestString.push(String.fromCharCode(ch));
// Return shortestString
return shortestString.join("");
}
}
return shortestString.join("");
}
// Driver Code
// Given String
var str = "abcdefghijklmnopqrstuvwxyzaabbccdd";
document.write( ShortestSubsequenceNotPresent(str));
</script>
Producción
ze
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hitesh_tripathi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA