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 ( ). 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', ' '};
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
- Iterate over all of the Strings.
- Iterate from the end of the text to generate various substrings.
- To the list, add the substring
- To construct a separate subsequence, remove the kth character from the substring
- acquired above.
- 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 read our more tutorial related to programming stuffs.