Given a non-empty string S containing only lowercase letters, print all ‘Special Subsequences’ of S. For Instance, “ab” has the following Special Subsequences-: { “A”, “AB”, “Ab”, “B”, “a”, “aB”, “ab”, “b” }.
Note : Consider only the non-empty special Subsequences of S.
Examples:
Input : S = "a"
Output : { "A", "a" }
Input : S = "ab"
Output : { "A", "AB", "Ab", "B", "a", "aB", "ab", "b" }
Prerequisite : Subsequences of String
Approach : This is a slight variation, to the classic problem, printing the subsequences of a string. Let’s say we have a recursive function generateSubsequences(input, i) that prints all the special subsequences of input string upto ith position. Let the current position be i in the input string, then there are three possibilities:
- Include input[i] in the output string as it is and call generateSubsequences(input, i + 1)
- Exclude input[i] in the output string and call generateSubsequence(str, i + 1), or
- Include the upper case form of input[i] and call generateSubsequences(str, i + 1). Do remember to first remove the currently added character from the output string.
Below is the implementation of above approach.
C++
// C++ Program to find all special subsequences// of the given type#include <bits/stdc++.h>using namespace std;// Function to generate the required subsequencesvoid generateSubsequences(string input, string output, int idx, vector<string>& ans){ // If the index pointer has reached the // end of input string if (input[idx] == '\0') { // Skip empty (" ") subsequence if (output.size()) ans.push_back(output); return; } // Exclude current character in output string generateSubsequences(input, output, idx + 1, ans); // Include current character in output string output += input[idx]; generateSubsequences(input, output, idx + 1, ans); // Remove the current included character and // and include it in its uppercase form output.pop_back(); char upper = input[idx]; upper = toupper(upper); output += upper; generateSubsequences(input, output, idx + 1, ans);}// Function to print the required subsequencesvoid printSubsequences(string S){ // Output String to store every subsequence string output; // Set of strings that will store all special // subsequences in lexicographical sorted order vector<string> ans; generateSubsequences(S, output, 0, ans); // Sort the strings to print in sorted order sort(ans.begin(), ans.end()); for (auto str : ans) cout << str << " ";}// Driver Codeint main(){ string S = "ab"; printSubsequences(S); return 0;} |
Java
// Java Program to find all special subsequences// of the given typeimport java.util.*;import java.io.*;public class SpecialSubsequences { // Function to generate the required subsequences public static void generateSubsequences(String input, String output, int index, ArrayList<String> ans) { // If the index pointer has reached the // end of input string if(index == input.length()){ // Skip empty (" ") subsequence if(output.length() != 0){ ans.add(output); } return; } //Exclude the character in the output string generateSubsequences(input, output, index+1, ans); //Include the current character as it is output += String.valueOf(input.charAt(index)); generateSubsequences(input, output, index+1, ans); //Include the current character in its upper case form //To remove the last character, we generate a substring till the //second last character output = output.substring(0, output.length()-1); output += String.valueOf( Character.toUpperCase(input.charAt(index))); generateSubsequences(input, output, index+1, ans); } // Function to print the required subsequences public static void printSubsequences(String s){ // Output String to store every subsequence String output = ""; // Set of strings that will store all special // subsequences in lexicographical sorted order ArrayList<String> ans = new ArrayList<>(); generateSubsequences(s, output, 0, ans); //Sort the strings to print in the sorted order Collections.sort(ans); for(String str: ans){ System.out.print(str+" "); } System.out.println(); } //Driver code public static void main(String[] args){ String s = "ab"; printSubsequences(s); }} |
Python3
# Python3 program to find all special subsequences# of the given typefrom typing import List# Function to generate the required subsequencesdef generateSubsequences(input: str, output: str, idx: int, ans: List[str]) -> None: # If the index pointer has reached the # end of input string if idx == len(input): # Skip empty (" ") subsequence if (len(output)): ans.append(output) return # Exclude current character in output string generateSubsequences(input, output, idx + 1, ans) # Include current character in output string output += input[idx] generateSubsequences(input, output, idx + 1, ans) # Remove the current included character and # and include it in its uppercase form output = output[:-1] upper = input[idx] upper = upper.upper() output += upper generateSubsequences(input, output, idx + 1, ans)# Function to print the required subsequencesdef printSubsequences(S: str) -> None: # Output String to store every subsequence output = "" # Set of strings that will store all special # subsequences in lexicographical sorted order ans = [] generateSubsequences(S, output, 0, ans) # Sort the strings to print in sorted order ans.sort() for string in ans: print(string, end = " ")# Driver Codeif __name__ == "__main__": S = "ab" printSubsequences(S)# This code is contributed by sanjeev2552 |
C#
// C# Program to find all special subsequences// of the given typeusing System;using System.Collections.Generic;public class SpecialSubsequences { // Function to generate the required subsequences public static void generateSubsequences(string input, string output, int index, List<string> ans) { // If the index pointer has reached the // end of input string if(index == input.Length){ // Skip empty (" ") subsequence if(output.Length != 0){ ans.Add(output); } return; } //Exclude the character in the output string generateSubsequences(input, output, index+1, ans); //Include the current character as it is output += input[index]; generateSubsequences(input, output, index+1, ans); //Include the current character in its upper case form //To remove the last character, we generate a substring till the //second last character output = output.Substring(0, output.Length-1); output += char.ToUpper(input[index]); generateSubsequences(input, output, index+1, ans); } // Function to print the required subsequences public static void printSubsequences(string s){ // Output string to store every subsequence string output = ""; // Set of strings that will store all special // subsequences in lexicographical sorted order List<string> ans = new List<string>(); generateSubsequences(s, output, 0, ans); //Sort the strings to print in the sorted order ans.Sort(StringComparer.Ordinal); foreach(string str in ans){ Console.Write(str+" "); } Console.WriteLine(); } //Driver code public static void Main(){ string s = "ab"; printSubsequences(s); }}// This code is contributed by Utkarsh |
Javascript
// Javascript Program to find all special subsequences// of the given type// Function to generate the required subsequencesfunction generateSubsequences(input, output,idx, ans){ // If the index pointer has reached the // end of input string if (idx == input.length) { // Skip empty (" ") subsequence if (output.length) ans.push(output); return; } // Exclude current character in output string generateSubsequences(input, output, idx + 1, ans); // Include current character in output string output += input[idx]; generateSubsequences(input, output, idx + 1, ans); // Remove the current included character and // and include it in its uppercase form output=output.slice(0,-1); let upper = input[idx]; upper = upper.toUpperCase(); output += upper; generateSubsequences(input, output, idx + 1, ans);}// Function to print the required subsequencesfunction printSubsequences(S){ // Output String to store every subsequence let output=""; // Set of strings that will store all special // subsequences in lexicographical sorted order let ans=[]; generateSubsequences(S, output, 0, ans); // Sort the strings to print in sorted order ans.sort(); for (let str in ans) console.log(ans[str]+" ");}// Driver Code let S = "ab"; printSubsequences(S);// This code is contributed by Pushpesh Raj. |
Output
A AB Ab B a aB ab b
Time Complexity : O(3N), where N is the size of string.
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!
