Given a string str of length N, the task is to print all possible distinct subsequences of the string str which consists of non-repeating characters only.
Examples:
Input: str = “abac”
Output: a ab abc ac b ba bac bc c
Explanation:
All possible distinct subsequences of the strings are { a, aa, aac, ab, aba, abac, abc, ac, b, ba, bac, bc, c }
Therefore, the subsequences consisting non-repeating characters only are { a, ab, abc, ac, b, ba, bac, bc, c }Input: str = “aaa”
Output: a
Approach: The problem can be solved using Backtracking technique using the following recurrence relation:
FindSub(str, res, i) = { FindSub(str, res, i + 1), FindSub(str, res + str[i], i + 1) }
res = subsequence of the string
i = index of a character in str
Follow the steps below to solve the problem:
- Initialize a Set, say sub, to store all possible subsequences consisting of non-repeating characters.
- Initialize another Set, say ch, to check if a character is present in the subsequence or not.
- Traverse the string and print all possible subsequences consisting of non-repeating characters only using the above recurrence relation.
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 find all the subsequences of// the string with non-repeating charactersvoid FindSub(set<string>& sub, set<char>& ch, string str, string res, int i){ // Base case if (i == str.length()) { // Insert current subsequence sub.insert(res); return; } // If str[i] is not present // in the current subsequence if (!ch.count(str[i])) { // Insert str[i] into the set ch.insert(str[i]); // Insert str[i] into the // current subsequence res.push_back(str[i]); FindSub(sub, ch, str, res, i + 1); // Remove str[i] from // current subsequence res.pop_back(); // Remove str[i] from the set ch.erase(str[i]); } // Not including str[i] from // the current subsequence FindSub(sub, ch, str, res, i + 1);}// Utility function to print all subsequences// of string with non-repeating charactersvoid printSubwithUniqueChar(string str, int N){ // Stores all possible subsequences // with non-repeating characters set<string> sub; // Stores subsequence with // non-repeating characters set<char> ch; FindSub(sub, ch, str, "", 0); // Traverse all possible subsequences // containing non-repeating characters for (auto subString : sub) { // Print subsequence cout << subString << " "; }}// Driver Codeint main(){ string str = "abac"; int N = str.length(); printSubwithUniqueChar(str, N); return 0;} |
Java
// Javs program to implement// the above approachimport java.util.*;class GFG { // Function to find all the subsequences of // the string with non-repeating characters public static void FindSub(HashSet<String> sub, HashSet<Character> ch, String str, String res, int i) { // Base case if (i == str.length()) { // Insert current subsequence sub.add(res); return; } // If str[i] is not present // in the current subsequence if (!ch.contains(str.charAt(i))) { // Insert str[i] into the set ch.add(str.charAt(i)); // Insert str[i] into the // current subsequence FindSub(sub, ch, str, res + str.charAt(i), i + 1); // Remove str[i] from the set ch.remove(str.charAt(i)); } // Not including str[i] from // the current subsequence FindSub(sub, ch, str, res, i + 1); } // Utility function to print all subsequences // of string with non-repeating characters public static void printSubwithUniqueChar(String str, int N) { // Stores all possible subsequences // with non-repeating characters HashSet<String> sub = new HashSet<>(); // Stores subsequence with // non-repeating characters HashSet<Character> ch = new HashSet<>(); FindSub(sub, ch, str, "", 0); // Traverse all possible subsequences // containing non-repeating characters for (String subString : sub) { // Print subsequence System.out.print(subString + " "); } } // Driver Code public static void main(String args[]) { String str = "abac"; int N = str.length(); printSubwithUniqueChar(str, N); }} |
Python3
# Python 3 program to implement# the above approach1# Function to find all the subsequences of# the string with non-repeating charactersdef FindSub(sub, ch1, str1, res, i): # Base case if (i == len(str1)): # Insert current subsequence sub.add(res) return # If str1[i] is not present # in the current subsequence if (str1[i] not in ch1): # Insert str1[i] into the set ch1.add(str1[i]) # Insert str1[i] into the # current subsequence FindSub(sub, ch1, str1, res+str1[i], i + 1) res += str1[i] # Remove str1[i] from # current subsequence res = res[0:len(res) - 1] # Remove str1[i] from the set ch1.remove(str1[i]) # Not including str1[i] from # the current subsequence FindSub(sub, ch1, str1, res, i + 1)# Utility function to print all subsequences# of string with non-repeating charactersdef printSubwithUniquech1ar(str1, N): # Stores all possible subsequences # with non-repeating characters sub = set() # Stores subsequence with # non-repeating characters ch1 = set() FindSub(sub, ch1, str1, "", 0) # Traverse all possible subsequences # containing non-repeating characters temp = [] for substring in sub: temp.append(substring) temp.sort(reverse = False) for x in temp: # Print subsequence print(x, end = " ")# Driver Codeif __name__ == '__main__': str2 = "abac" N = len(str2) printSubwithUniquech1ar(str2, N) # This code is contributed by bgangwar59. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find all the subsequences of // the string with non-repeating characters public static void FindSub(HashSet<String> sub, HashSet<char> ch, String str, String res, int i) { // Base case if (i == str.Length) { // Insert current subsequence sub.Add(res); return; } // If str[i] is not present // in the current subsequence if (!ch.Contains(str[i])) { // Insert str[i] into the set ch.Add(str[i]); // Insert str[i] into the // current subsequence FindSub(sub, ch, str, res + str[i], i + 1); // Remove str[i] from the set ch.Remove(str[i]); } // Not including str[i] from // the current subsequence FindSub(sub, ch, str, res, i + 1); } // Utility function to print all subsequences // of string with non-repeating characters public static void printSubwithUniqueChar(String str, int N) { // Stores all possible subsequences // with non-repeating characters HashSet<String> sub = new HashSet<String>(); // Stores subsequence with // non-repeating characters HashSet<char> ch = new HashSet<char>(); FindSub(sub, ch, str, "", 0); // Traverse all possible subsequences // containing non-repeating characters foreach (String subString in sub) { // Print subsequence Console.Write(subString + " "); } } // Driver Code public static void Main(String []args) { String str = "abac"; int N = str.Length; printSubwithUniqueChar(str, N); }}// This code contributed by shikhasingrajput |
Javascript
<script>// JavaScript program to implement// the above approach// Stores all possible subsequences// with non-repeating charactersvar sub = new Set();// Stores subsequence with// non-repeating charactersvar ch = new Set();// Function to find all the subsequences of// the string with non-repeating charactersfunction FindSub(str, res, i){ // Base case if (i == str.length) { // Insert current subsequence sub.add(res.join("")); return; } // If str[i] is not present // in the current subsequence if (!ch.has(str[i])) { // Insert str[i] into the set ch.add(str[i]); // Insert str[i] into the // current subsequence res.push(str[i]); FindSub(str, res, i + 1); res.pop() // Remove str[i] from the set ch.delete(str[i]); } // Not including str[i] from // the current subsequence FindSub(str, res, i + 1);}// Utility function to print all subsequences// of string with non-repeating charactersfunction printSubwithUniqueChar(str, N){ FindSub(str, [], 0); var tmp = [...sub].sort(); // Traverse all possible subsequences // containing non-repeating characters tmp.forEach(subString => { // Print subsequence document.write( subString + " "); });}// Driver Codevar str = "abac";var N = str.length;printSubwithUniqueChar(str, N);</script> |
Output:
a ab abc ac b ba bac bc c
Time complexity: O(N * log(N) * 2N)
Auxiliary Space O(N * 2N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
