Sudo Placement | Special Subsequences | Java Program to find all special subsequences of the given type ; Function to generate the required subsequences ; If the index pointer has reached the end of input string ; Skip empty ( " ▁ " ) subsequence ; Exclude the character in the output string ; Include the current character as it is ; Include the current character in its upper case form To remove the last character , we generate a substring till the second last character ; Function to print the required subsequences ; Output String to store every subsequence ; Set of strings that will store all special subsequences in lexicographical sorted order ; Sort the strings to print in the sorted order ; Driver code
import java . util . * ; import java . io . * ; public class SpecialSubsequences { public static void generateSubsequences ( String input , String output , int index , ArrayList < String > ans ) { if ( index == input . length ( ) ) { if ( output . length ( ) != 0 ) { ans . add ( output ) ; } return ; } generateSubsequences ( input , output , index + 1 , ans ) ; output += String . valueOf ( input . charAt ( index ) ) ; generateSubsequences ( input , output , index + 1 , ans ) ; output = output . substring ( 0 , output . length ( ) - 1 ) ; output += String . valueOf ( Character . toUpperCase ( input . charAt ( index ) ) ) ; generateSubsequences ( input , output , index + 1 , ans ) ; } public static void printSubsequences ( String s ) { String output = " " ; ArrayList < String > ans = new ArrayList < > ( ) ; generateSubsequences ( s , output , 0 , ans ) ; Collections . sort ( ans ) ; for ( String str : ans ) { System . out . print ( str + " ▁ " ) ; } System . out . println ( ) ; } public static void main ( String [ ] args ) { String s = " ab " ; printSubsequences ( s ) ; } }