Subsequences of String

Introduction

It is recommended that before reading this article, you should be familiar with the concepts

of recursion and string. Understanding methods like substr, empty, subscript, and indexing

will help you.

In C++, what is a String?

In C++, a string is an object that represents a group (or series) of various characters. Strings

are part of the standard string class in C++ (std::string). A string's character are stored as a

collection of bytes in contiguous memory regions by the string class. Strings are most

typically employed in programmes that need text manipulation. In C++, we may execute a

variety of operations on strings. For instance, reversing, concatenating, or sending a function

as an argument.

Syntax

The syntax for creating a string in C++ is straightforward. In C++, the string keyword is used

to produce a string. Before we can use this keyword, we must first include the standard

string class in our application.

string str_name = "This is a C++ string";

C++ strings can be produced in a variety of methods, in addition to the approach given

above. In the next sections, we'll go over the several ways to define a string. Before we get

started, let's have a look at the C Style Character Strings.

The Character String in C-Style

A string is defined as an array of characters that terminates with a null or termination

character in the C computer language (\0). The termination is significant since it informs the

compiler of the string's conclusion. The C-style strings are likewise supported by C++.

Syntax

We can build C style strings in the same way that we can create an integer array. The syntax

is as follows.

char str_array[7] = {'C', 'o', 'd', 'i', 'n', 'g', '\0'};

The array's length is one longer than the length of the string since we have to include a null

character. Alternatively, we may define the preceding string as follows:

char str_array[] = "Ninjas";

Because C++ inserts a null character at the end of the string, the array str array will still have

7 characters. When we use the sizeof() method to determine the size of the array above, we

get 7.

Concatenation: 

Concatenation of strings is the process of joining two or more strings together to create a

new string. If we want to concatenate two or more strings, C++ has the facility to accomplish

so.

There are three techniques to concatenate strings in C++. The following are the details.

1. strcat() function usage

We must include the cstring header file in our application to utilise the strcat() method. Two

character arrays are sent to the strcat() method as input. The second array is concatenated

to the end of the first array.

strcat has the following syntax:

strcat(char_array1, char_array2);

It's worth noting that the strcat() method only accepts character arrays as input. The method

does not allow us to utilise string objects.

For example

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char str1[] = "Ninjas ";

char str2[] = "Topics.";

strcat(str1, str2);

cout << str1 << endl;

return 0;

}

2. Making use of the append() method

The add() method joins the first and second strings together. This method makes use of

variables of type string. This function's syntax is as follows:

#include <iostream>

using namespace std;

int main() {

string str1 = "Ninjas ";

string str2 = "Topics.";

str1.append(str2);

cout << str1 << endl;

return 0;

}

3. Making use of the '+' operator

Concatenating strings in this manner is the simplest method. The + operator concatenates

two (or more) strings and returns the result. Its syntax is as follows:

str1 + str2 + str3

Consider the following scenario:

#include <iostream>

using namespace std;

int main() {

string str1 = "Scaler ";

string str2 = "Topics.";

str1 = str1 + str2;

cout << str1 << endl;

return 0;

}

Whether to use + or add is up to the coder (). The add() method is significantly quicker than

+. In applications with short strings, however, substituting + with add() has no major impact

on programme performance. The strcat() function, on the other hand, has some potential

performance difficulties due to its temporal complexity and the amount of times it is called in

the application. In a nutshell, the add() method or the + operator are the best options.

Problem Description

First, try to solve the problem on your own related to subsequences of string in the code

editors.

You're given a string called str that contains lowercase English letters ranging from a to z.

It's your job to find all non-empty subsequences of str.

Note: A string's subsequence is created by removing 0 or more letters from the string while

leaving the remaining letters in the same order.

Input Format:

Each test case starts with the string str on the first and only line.

Output Format:

Print the subsequences of the string str separated by space for each test case in the output

format. Each test case's output appears on its line. In any order, the output strings can be

returned.

Constraints:

1 <= T <= 10

1 <= |STR| <= 16

Where |STR| represents the length of the string 'STR.'

Time Limit: 1 sec

Sample Input 1:

1 abc

Sample Output 1:

a ab abc ac b bc c

Explanation Of Sample Input 1: All possible subsequences of abc are: “a” , “b”, “c”, “ab”,

“bc”, “ac”, “abc”

Sample Input 2:

1 bbb

Sample Output 2:

b b b bb bb bb bbb

Method 1:

We are using the concept of pick and non-pick. The Idea is simply recursively calling

function one by picking an element from the given array and not picking it.

// C++ program for the above approach

#include <bits/stdc++.h>

using namespace std;

vector<string> ans;

void getSubsequence(string input, string output)

{

/* Base Case

Print the output string if the input is empty. */

if (input.empty()) {

ans.push_back(output);

return;

}

/*The output string includes

the Iast character from the input string. */

printSubsequence(input.substr(1), output + input[0]);

/* The last character of the input string

is not included in the output. */

printSubsequence(input.substr(1), output);

}

int main()

{

string out = ""; // output

string str = "abcd"; // input

getSubsequence(str, output);

/* Use ans vector inside main. */

for(string a : ans) cout<<output;

return 0;

}

Method 2: Algorithm

1. Iterate over all of the Strings.
2. Iterate from the end of the text to generate various substrings.
3. To the list, add the substring
4. To construct a separate subsequence, remove the kth character from the substring
5. acquired above.
6. Recur if the subsequence isn't in the list.

// Code

#include <bits/stdc++.h>

using namespace std;

// configured to keep track of all subsequences

unordered_set<string> st;

// This function calculates all of a string's subsequences.

void getSubsequence(string str)

{

for (int i = 0; i < str.length(); i++) {

/* To generate substrings, iterate

from the end of the string. */

for (int j = str.length(); j > i; j--) {

string sub_str = str.substr(i, j);

st.insert(sub_str);

/* Drop the kth character in the substring,

and if it isn't in the set, repeat. */

for (int k = 1; k < sub_str.length(); k++) {

string sb = sub_str;

// Drop character from the string

sb.erase(sb.begin() + k);

getSubsequence(sb);

}

}

}

}

int main()

{

string s = "abbc";

getSubsequence(s);

for (auto itr : st)

cout << itr << " ";

cout << endl;

return 0;

}

Final Verdict

Hope you like this article, we have covered this topic in-depth here if you want to explore the String and Recursion topic in more detail then you can visit Coding Ninjas official website.