Subsequences generated by including characters or ASCII value of characters of given string

0 0 5 minutes read

Given a string str of length N, the task is to print all possible non-empty subsequences of the given string such that the subsequences either contains characters or ASCII value of the characters from the given string.

Examples:

Input: str = “ab”
Output: b 98 a ab a98 97 97b 9798
Explanation:
Possible subsequence of the strings are { b, a, ab }.
Possible subsequences of the string generated by including either the characters or the ASCII value of the characters from the given string are { 98, b, a, 97, ab, 97b, a98, 9798 }.
Therefore, the required output is { b, 98, a, ab, a98, 97, 97b, 9798 }.

Input: str = “a”
Output: a 97

Approach: Follow the steps below to solve the problem:

Iterate over each character of the given string using variable i to generate all possible subsequences of the string.
For every i^th character, the following three operations can be performed:
- Include the i^th character of str in a subsequence.
- Do not include the i^th character of str in a subsequence.
- Include the ASCII value of i^th character of str in a subsequence.
Therefore, the recurrence relation to solve this problem is as follows:

FindSub(str, res, i) = { FindSub(str, res, i + 1), FindSub(str, res + str[i], i + 1), FindSub(str, res + ASCII(str[i]), i + 1) }
res = subsequence of the string
i = index of a character in str

Using the above recurrence relation, print all possible subsequences based on the given conditions.

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 print subsequences containing
// ASCII value of the characters or the
// the characters of the given string
void FindSub(string str, string res,
             int i)
{
     
    // Base Case
    if (i == str.length())
    {
         
        // If length of the
        // subsequence exceeds 0
        if (res.length() > 0)
        {
             
            // Print the subsequence
           cout << res << " ";
        }
        return;
    }
 
    // Stores character present at
    // i-th index of str
    char ch = str[i];
 
    // If the i-th character is not
    // included in the subsequence
    FindSub(str, res, i + 1);
 
    // Including the i-th character
    // in the subsequence
    FindSub(str, res + ch, i + 1);
 
    // Include the ASCII value of the
    // ith character in the subsequence
    FindSub(str, res + to_string(int(ch)), i + 1);
}
 
// Driver Code
int main()
{
    string str = "ab";
    string res = "";
     
    // Stores length of str
    int N = str.length();
 
    FindSub(str, res, 0);
}
 
// This code is contributed by ipg2016107

Java

// Java program to implement
// the above approach
class GFG {
 
    // Function to print subsequences containing
    // ASCII value of the characters or the
    // the characters of the given string
    static void FindSub(String str, String res,
                        int i)
    {
        // Base Case
        if (i == str.length()) {
 
            // If length of the
            // subsequence exceeds 0
            if (res.length() > 0) {
 
                // Print the subsequence
                System.out.print(res + " ");
            }
            return;
        }
 
        // Stores character present at
        // i-th index of str
        char ch = str.charAt(i);
 
        // If the i-th character is not
        // included in the subsequence
        FindSub(str, res, i + 1);
 
        // Including the i-th character
        // in the subsequence
        FindSub(str, res + ch, i + 1);
 
        // Include the ASCII value of the
        // ith character in the subsequence
        FindSub(str, res + (int)ch, i + 1);
        ;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        String str = "ab";
 
        String res = "";
 
        // Stores length of str
        int N = str.length();
 
        FindSub(str, res, 0);
    }
}

Python3

# Python3 program to implement
# the above approach
 
# Function to print subsequences containing
# ASCII value of the characters or the
# the characters of the given string
def FindSub(string , res, i) :
     
    # Base Case
    if (i == len(string)):
 
        # If length of the
        # subsequence exceeds 0
        if (len(res) > 0) :
             
            # Print the subsequence
            print(res, end=" ");
        
        return;
 
    # Stores character present at
    # i-th index of str
    ch = string[i];
 
    # If the i-th character is not
    # included in the subsequence
    FindSub(string, res, i + 1);
 
    # Including the i-th character
    # in the subsequence
    FindSub(string, res + ch, i + 1);
 
    # Include the ASCII value of the
    # ith character in the subsequence
    FindSub(string, res + str(ord(ch)), i + 1);
 
# Driver Code
if __name__ == "__main__" :
     
    string = "ab";
 
    res = "";
 
    # Stores length of str
    N = len(string);
 
    FindSub(string, res, 0);
   
# This code is contributed by AnkitRai01

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to print subsequences containing
// ASCII value of the characters or the
// the characters of the given string
static void FindSub(string str, string res,
                    int i)
{
     
    // Base Case
    if (i == str.Length) 
    {
         
        // If length of the
        // subsequence exceeds 0
        if (res.Length > 0)
        {
             
            // Print the subsequence
            Console.Write(res + " ");
        }
        return;
    }
 
    // Stores character present at
    // i-th index of str
    char ch = str[i];
 
    // If the i-th character is not
    // included in the subsequence
    FindSub(str, res, i + 1);
 
    // Including the i-th character
    // in the subsequence
    FindSub(str, res + ch, i + 1);
 
    // Include the ASCII value of the
    // ith character in the subsequence
    FindSub(str, res + (int)ch, i + 1);
}
 
// Driver Code
public static void Main(String[] args)
{
    string str = "ab";
    string res = "";
 
    // Stores length of str
    int N = str.Length;
 
    FindSub(str, res, 0);
}
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to print subsequences containing
// ASCII value of the characters or the
// the characters of the given string
function FindSub(str, res, i) 
{
     
    // Base Case
    if (i === str.length) 
    {
 
        // If length of the
        // subsequence exceeds 0
        if (res.length > 0)
        {
             
            // Print the subsequence
            document.write(res + " ");
        }
        return;
    }
 
    // Stores character present at
    // i-th index of str
    var ch = str[i];
     
    // If the i-th character is not
    // included in the subsequence
    FindSub(str, res, i + 1);
     
    // Including the i-th character
    // in the subsequence
    FindSub(str, res + ch, i + 1);
     
    // Include the ASCII value of the
    // ith character in the subsequence
    FindSub(str, res + ch.charCodeAt(0), i + 1);
}
 
// Driver Code
var str = "ab";
var res = "";
 
// Stores length of str
var N = str.length;
 
FindSub(str, res, 0);
 
// This code is contributed by rdtank
 
</script>

Output:

b 98 a ab a98 97 97b 9798

Time Complexity: O(3^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 zambiatek!