Given a string str, consisting of lowercase alphabets, the task is to find the shortest string which is not a subsequence of the given string. If multiple strings exist, then print any one of them.
Examples:
Input: str = “abaabcc”
Output: d
Explanation:
One of the possible shortest string which is not a subsequence of the given string is “d”. Therefore, the required output is “d”.Input: str = “abcdefghijklmnopqrstuvwxyzaabbccdd”
Output: ze
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Initialize a string, say shortestString, to store the shortest string which is not a subsequence of the given string.
- Initialize a Set, say segments, to store all possible characters of each subsegment.
- Traverse the string and insert the character of the string into segments and check if the segments contain all the lowercase alphabets or not. If found to be true, then append the current character into shortestString and remove all the elements from the segments.
- Iterate over all possible lowercase alphabets in the range [a – z] and check if the current character is present in the segment or not. If found to be true, then insert the current character into shortestString.
- Finally, print the value of shortestString.
Below is the implementation of the above approach:
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 stringstring 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 Codeint main(){ // Given String string str = "abcdefghijklmnopqrstuvwxyzaabbccdd"; cout << ShortestSubsequenceNotPresent(str); return 0;} |
Java
// Java program to implement// the above approachimport 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 stringdef 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 StringStr = "abcdefghijklmnopqrstuvwxyzaabbccdd"print(ShortestSubsequenceNotPresent(Str))# This code is contributed by divyeshrabadiya07 |
C#
// C# program to implement// the above approachusing 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 Codepublic 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 stringfunction 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 Stringvar str = "abcdefghijklmnopqrstuvwxyzaabbccdd";document.write( ShortestSubsequenceNotPresent(str));</script> |
Output
ze
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
