Colocación de Sudo | Subsecuencias especiales

Dada una string S no vacía que contiene solo letras minúsculas, imprima todas las ‘ Subsecuencias especiales ‘ de S. Por ejemplo, «ab» tiene las siguientes Subsecuencias especiales: { «A», «AB», «Ab», «B» , “a”, “aB”, “ab”, “b” }.

 Nota : Considere solo las subsecuencias especiales no vacías de S.

Ejemplos :  

Input : S = "a"
Output : { "A", "a" }

Input : S = "ab"
Output : { "A", "AB", "Ab", "B", "a", "aB", "ab", "b" }

Requisito previo : subsecuencias de string 

Enfoque : Esta es una ligera variación, al problema clásico, imprimiendo las subsecuencias de una string. Digamos que tenemos una función recursiva generar subsecuencias (entrada, i) que imprime todas las subsecuencias especiales de la string de entrada hasta la i ^-ésima posición. Deje que la posición actual sea i en la string de entrada, entonces hay tres posibilidades: 

1. Incluya input[i] en la string de salida tal como está y llame a generateSubsequences(input, i + 1)
2. Excluya input[i] en la string de salida y llame a generateSubsequence(str, i + 1), o
3. Incluya la forma en mayúsculas de input[i] y llame a generateSubsequences(str, i + 1). Recuerde eliminar primero el carácter agregado actualmente de la string de salida.

A continuación se muestra la implementación del enfoque anterior.

// C++ Program to find all special subsequences
// of the given type
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate the required subsequences
void 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 subsequences
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
    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 Code
int main()
{
    string S = "ab";
    printSubsequences(S);
    return 0;
}

// Java Program to find all special subsequences
// of the given type
import 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 program to find all special subsequences
# of the given type
from typing import List
 
# Function to generate the required subsequences
def 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 subsequences
def 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 Code
if __name__ == "__main__":
 
    S = "ab"
     
    printSubsequences(S)
 
# This code is contributed by sanjeev2552

Salida :  

A AB Ab B a aB ab b

Complejidad de tiempo : O (3 ^N ), donde N es el tamaño de la string.