HackerRank Coding Question for Placements 4

June 24, 2019

Write a program to print all Subsequences of String which Start with Vowel and End with Consonant

Given a string return all possible subsequences which start with vowel and end with a consonant. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.
Examples:

Input : ‘abc’
Output : ab, ac, abc

Input : ‘aab’
Output : ab, aab

xplanation of the Algorithm:

Step 1: Iterate over the entire String
Step 2: check if the ith character for vowel
Step 3: If true iterate the string from the end,
        if false move to next iteration
Step 4: check the jth character for consonent
        if false move to next iteration 
        if true perform the following 
Step 5: Add the substring starting at index i and
        ending at index j to the hastset.
Step 6: Iterate over the substring drop each character 
        and recur to generate all its subString
// Java Program to generate all the subsequence
// starting with vowel and ending with consonant.
import java.util.HashSet;
public class Subsequence {
    // Set to store all the subsequences
    static HashSet<String> st = new HashSet<>();
    // It computes all the possible substring that
    // starts with vowel and end with consonent
    static void subsequence(String str)
    {
        // iterate over the entire string
        for (int i = 0; i < str.length(); i++) {
        
            // test ith character for vowel
            if (isVowel(str.charAt(i))) {
        
                // if the ith character is vowel
                // iterate from end of the string
                // and check for consonant.
                for (int j = (str.length() - 1); j >= i; j--) {
                    
                    // test jth character for consonant.
                    if (isConsonant(str.charAt((j)))) {
                    
                        // once we get a consonant add it to
                        // the hashset
                        String str_sub = str.substring(i, j + 1);
                        st.add(str_sub);
                        // drop each character of the substring
                        // and recur to generate all subsquence
                        // of the substring
                        for (int k = 1; k < str_sub.length() - 1; k++) {
                            StringBuffer sb = new StringBuffer(str_sub);
                            sb.deleteCharAt(k);
                            subsequence(sb.toString());
                        }
                    }
                }
            }
        }
    }
    // Utility method to check vowel
    static boolean isVowel(char c)
    {
        return (c == 'a' || c == 'e' || c == 'i' || c == 'o'
                                              || c == 'u');
    }
    // Utility method to check consonant
    static boolean isConsonant(char c)
    {
        return !(c == 'a' || c == 'e' || c == 'i' || c == 'o'
                                              || c == 'u');
    }
    // Driver code
    public static void main(String[] args)
    {
        String s = "xabcef";
        subsequence(s);
        System.out.println(st);
    }
}

Output:

[ef, ab, ac, aef, abc, abf, af, acf, abcef, abcf, acef, abef]

One comment on “HackerRank Coding Question for Placements 4”