Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Example
1.1.1.
Input
1.1.2.
Output
2.
Approach 1
2.1.
C++ implementation
2.1.1.
Output
2.2.
Java implementation
2.2.1.
Output
2.2.2.
Complexities
3.
Approach 2
3.1.
C++ implementation
3.1.1.
Output
3.2.
Java implementation
3.2.1.
Output
3.3.
Complexities
3.3.1.
Time complexity
3.3.2.
Space complexity 
4.
Approach 3
4.1.
C++ implementation
4.1.1.
Output
4.2.
Java implementation
4.2.1.
Output
4.3.
Complexities
4.3.1.
Time complexity
4.3.2.
Space complexity 
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Print all subsequences of a string

Author Manan Singhal
8 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

We must find all subsequences of a string given to us as an input. The string subsequence of a given string is created by removing a single character from a string without changing its order.

Example

Input

abc

Output

a, b, c, ab, bc, ac, abc

Recommended topic, kth largest element in an array, and Euclid GCD Algorithm

Approach 1

Pick and Don't Pick Concept

  • Iterate over the string.
  • Now, add first character to output and remove that character from input and repeat the procedure until input string becomes empty.
  • Similarly, skipped the first character to output and also, remove the character from input and repeat the procedure until input string becomes empty.

C++ implementation

/* C++ program to print all subsequences of a string */
#include <bits/stdc++.h>
using namespace std;

/* Finding all subsequences from an input string */
void printSubsequence(string input, string output)
{
if (input.empty()) {
cout << output << endl;
return;
}

/* output is passed with 
      including the 1st character of
      input string */
printSubsequence(input.substr(1), output + input[0]);

/* output is passed without
including the 1st character
of Input string */
printSubsequence(input.substr(1), output);
}

/* Main code */
int main()
{
/* empty string passed as an output parameter */
string output = "";
string input = "abcd";
printSubsequence(input, output);

return 0;
}

Output

abcd
abc
abd
ab
acd
ac
ad
a
bcd
bc
bd
b
cd
c
d

Java implementation

/* Java program to print all subsequences of a string */
import java.util.*;
class Main {

/* Declared a global list */
static List<String> al = new ArrayList<>();

/* Creating a public static ArrayList to store values */
public static void main(String[] args)
{
String s = "abcd";
findsubsequences(s, "");
System.out.println(al);
}

private static void findsubsequences(String s,
String ans)
{
if (s.length() == 0) {
al.add(ans);
return;
}

/* Adding 1st character in string */
/* Not adding 1st character of the string
  because the concept of subsequence either
  character will present or not */
findsubsequences(s.substring(1), ans + s.charAt(0));
findsubsequences(s.substring(1), ans);
}
}

Output

[abcd, abc, abd, ab, acd, ac, ad, a, bcd, bc, bd, b, cd, c, d, ]

Complexities

Time complexity

O(2n), where n is the length of the string
Reason: Total 2n recursive functions to be called, and each function has O(1) time complexity. Thus, the total time complexity for this program will be O(2n)

Space complexity 

O(1)
Reason: No extra variable space is needed.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2

  • Iterate over all of the Strings.
  • Iterate from the end 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.

C++ implementation

/* C++ program to print all subsequences of a string */
#include <bits/stdc++.h>
using namespace std;

/* set to store and print all subsequences */
unordered_set<string> st;

/* Function computes all the subsequence of a string */
void subsequence(string str)
{
/* Iterate over the entire string */
      int i;
for (i = 0; i < str.length(); i++) {

/* 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 kth character in the substring
  and if it’s not in the set then recur */
for (int k = 1; k < sub_str.length(); k++) {
string sb = sub_str;

/* Drop character from the string */
sb.erase(sb.begin() + k);
subsequence(sb);
}
}
}
}

/* Main Code */
int main()
{
string s = "abcd";
subsequence(s);
for (auto i : st)
cout << i << " ";
cout << endl;

return 0;
}

Output

bcd bc abcd acd ab a abd ad d ac cd c b bd abc

Java implementation

/* Java Program to print all subsequences of a string */
import java.util.HashSet;

public class Main {

/* Set to store and print all subsequences */
static HashSet<String> st = new HashSet<>();

/* Function computes all the subsequence of an string */
static void subsequence(String str)
{
/* Iterate over the entire string */
            int i;
for (i = 0; i < str.length(); i++) {

/* Iterate from the end of the string */
for (int j = str.length(); j > i; j--) {
String sub_str = str.substring(i, j);

if (!st.contains(sub_str))
st.add(sub_str);

/* Drop kth character in the substring
  and if it’s not in the set then recur */
for (int k = 1; k < sub_str.length() - 1;
k++) {
StringBuffer sb
= new StringBuffer(sub_str);

/* Drop character from the string */
sb.deleteCharAt(k);
if (!st.contains(sb))
;
subsequence(sb.toString());
}
}
}
}

/* Main code */
public static void main(String[] args)
{
String s = "abcd";
subsequence(s);
System.out.println(st);
}
}

Output

[a, cd, ab, bc, ac, abd, bd, b, bcd, acd, ad, c, abc, d, abcd]

Complexities

Time complexity

O(n5log n), where n is the length of the string
Reason: Total n2 recursive functions to be called, and each function has O(n3) time complexity and insert function in unordered map takes log n. Thus, the total time complexity for this program will be O(n5)

Space complexity 

O(n2), where n is the length of the string
Reason: Total n2 recursive functions to be called, and stored in an ordered map.

Read More - Time Complexity of Sorting Algorithms

Also check out - Substr C++

Approach 3

Fix characters one by one and recursively produce all subgroups from there. We eliminate the last character after each recursive call so that the next permutation can be formed. Thus, we print all subsequences of a given string.

  • Iterate over the string.
  • Now, use for loop to add all characters to output once and call the same function while resetting output to the previous value.
  • Print the output if it is not an empty string.

C++ implementation

/* C++ program to print all subsequences of a string */
#include <bits/stdc++.h>
using namespace std;

/* str: Stores input string
   n : length of string str.
  curr : Stores current permutation
  index : Index in current permutation, curr */
void printSubSeqRec(string str, int n, int index = -1,
string curr = "")
{
if (index == n)
return;

if (!curr.empty()) {
cout << curr << "\n";
}

for (int i = index + 1; i < n; i++) {

curr += str[i];
printSubSeqRec(str, n, i, curr);

/* backtracking */
curr = curr.erase(curr.size() - 1);
}
return;
}

/* Generates power set in lexicographic order. */
void printSubSeq(string str)
{
printSubSeqRec(str, str.size());
}

/* Main code */
int main()
{
string str = "abcd";
printSubSeq(str);
return 0;
}

Output

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

Java implementation

/* Java program to print all subsequences of a string */
class Main {

/* str: Stores input string
  n : length of string str.
  curr : Stores current permutation
  index : Index in current permutation, curr */
static void printSubSequenceRec(String str, int n, int index,
String curr)
{
if (index == n) {
return;
}
if (curr != null && !curr.trim().isEmpty()) {
System.out.println(curr);
}
int i;
for (i = index + 1; i < n; i++) {
curr += str.charAt(i);
printSubSequenceRec(str, n, i, curr);

curr = curr.substring(0, curr.length() - 1);
}
}

/* Generates power set in lexicographic order. */
static void printSubSequence(String str)
{
int index = -1;
String curr = "";

printSubSequenceRec(str, str.length(), index, curr);
}

/* Main code */
public static void main(String[] args)
{
String str = "abcd";
printSubSequence(str);
}
}

Output

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

Complexities

Time complexity

O(nn), where n is the length of the string
Reason: Total nn recursive functions to be called, and each function has O(1) time complexity. Thus, the total time complexity for this program will be O(nn)

Space complexity 

O(1)
Reason: No extra variable space is needed.

FAQs

  1. What is a subsequence?
    A subsequence is a sequence created by eliminating some characters from a string while keeping the order of the remaining characters the same.
     
  2. Difference between subsequence and substring?
    A substring is the contiguous part of the string. If a string is n characters long, the number of substrings equals n*(n+1)/2.
     
  3. What is a string in C++?
    A string is the sequence of characters in C++. C++ offers a string class with which you can store your string in an object.
     
  4. Is it possible to create a string object in C?
    No, you can only store your string as a character in an array in C. The C language lacks a string class, but C++ does.
     
  5. Does the strlen() function take into account null characters when calculating length?
    No, strlen() does not include null characters in the string length. It merely counts the length of the string's characters.

Key Takeaways

In this article, we have tried to print all possible sequences of a string. We hope that this question will help you understand the concept of string problems, and if you would like to learn more about it, check out our other problems on subsequences of a stringPrint All Subsequences Of A String.

Recommended Reads, Permutation of string

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Count of Increasing Substrings in given String
Next article
Maximize the Confusion of an Exam
Live masterclass