Special Sub-sequences
The main goal of this article is finding out all the special sub-sequences of a string. To generate Special Sub-sequences, we need to consider both the upper and lower cases and their combination. For Instance, “ab” has the following Special Sub-sequences-: { “A”, “AB”, “Ab”, “B”, “a”, “aB”, “ab”, “b” }.
For understanding what a special sub-sequence is, we need to know, what a sub-sequence is, and for that we need to know what a sequence is! Duh! Long story! Well, if you think so, then fortunately you are wrong.
Well a sequence basically means order, that is order of an arrangement. Suppose we have a string = “abc”. Here every character of the string is itself a sequence of length 1. We can call all such sequences as sub-sequences. Please note, an empty string is always a sub-sequence of a string.
Therefore, sub-sequences of different lengths are:
Length=0 : “”
Length=1 : a, b, c
Length=2 : ab, bc, ac
Length=3 : abc
Can we find any other sub-sequence? Well, you might be thinking, why not we have included ba, ca, cb as sub-sequences of length 2. The reason is, as I have mentioned in the beginning, in a sequence, order is important, we can’t change the original order of the elements. So now, you know the basic of a sub-sequence.
Next important thing to mention is: Is there is any difference between a sub-string and a sub-sequence. Well yes, in a sub-string, all the characters of the string must be contiguous, i.e. sub-string of length 2 is : ab and bc only. ac doesn’t count as a sub-string as in original string “abc”, element ‘a’ and element ‘c’ are not at contiguous locations.
Now, we are done with the basics and can move forward to the main goal of this article, that includes, finding all the sub-sequences of a string.
Now, we are starting on how to get all the sub-sequences of a string.
While traversing a string to find it’s sub-sequences, for every character, we can either include it or exclude it! Keep this point in mind. It’s important.
If a string is of a single character, it’s sub-sequences are empty string and the string itself. In the first case, we excluded the current character, and in latter case we included the current character. Like for example, in string “c”, it’s sub-sequences are “” and “c”.
Now going one step further, for string of length=2:
Say for example, the string s is “bc”. It’s sub-sequences will include “”, “c”, “b”, “bc”. We will start traversing the string from it’s right end. So, initially we have a string of length=1, s= “c”. In this case, we can either include it or exclude it, after doing so, we get two sub-sequences: “”, “c”. After that we move on to the next character from right end. The string length increases by 1 after each iteration. Now s= “bc”. We can either exclude b in sub-sequence,or include it. On excluding, sub-sequences will be “”, “c”, whereas after including it, sub-sequences will be “”, “b”, “bc”.
If we notice closely, we can see that:
sub-sequences(bc) = sub-sequences(c) and (character b concatenated to sub-sequences(c))
- sub-sequences(c) means excluding current_char “b”
- character b concatenated to sub-sequences(c)means {b+ “”}, {b+ “c”}, which means, including current_char “b”
Therefore, all the distinct sub-sequences are [“”, “b”, “c”, “bc”];
So we just need to find all the sub-sequences of the last character, which is simply, an empty string and the last character itself. Then, go one step back in the string, and find the character at this position. After that find all the sub-sequences by including the current character and by excluding the current character and repeat the same for all the characters of the string till we reach the first character of the string.
WRITING A PROGRAM FOR THE SAME
I am writing this from my post on geeksforgeeks.
Consider the first example, “ab”.
We start traversing the input string from it’s right end and take one character at a time. So, first char that we consider in input string “ab” is ‘b’. We store the sub-sequences in a vector called v1. Initially, v1 is empty. Now, for each character we traverse, we check if v1 is empty, if yes, we push an empty string and the current character into v1. This is done because, say we are at character ‘b’ and our list of sub-sequences i.e. v1 is empty, then the sub-sequences we can generate using only ‘b’ are “” and “b”.
After that we move onto the next character from right end of the input string, in this case, in input string “ab”, we reached the character ‘a’. Now sub-sequences of “ab” are “”, “a”, “b”, “ab”. Now if we look closely, we just need to add a new sub-sequence list to our previous list of sub-sequences, i.e. v1. New list can be created by concatenating the new char to the start of each sub-sequence of v1.
v1= “”,”b”
After appending ‘a’ to the start of each subsequence of v1, we get = “a”, “ab”
So, our new v1 would include the new list of sub-sequence and the old list of sub-sequence = “”, “a”, “ab”, “b”
But this problem demands our special care as it’s name suggest! ;)
In the special sub-sequence
We also have to take care of the case of the alphabet. Don’t worry, it’s very easy to implement.
When we start from the right end, we also push the UpperCase of B into the vector. So our v1 becomes = “”, “b”, “B”
Now, for each character we encounter while traversing the string from right to left, we also include it’s capital case. Like in this case:
v1 = “”, “b”, “B”
After appending ‘a’ to the start of each sub-sequence of v1, we get = “a”, “ab”, “aB”
After appending ‘A’ to the start of each sub-sequence of v1, we get = “A”, “Ab”, “AB”
So, our new v1 would include the new list of sub-sequence and the old list of sub-sequence = “”, “b”, “B”, “a”, “ab”, “aB”, “A”, “Ab”, “AB” which is our required result.
- Creating an empty list of sub-sequences.
string s= “ab”
vector<string> v1;
2. Create a map that will store all the distinct sub-sequences in a sorted order.
map<string, int> m1;
3. Define the sub-sequences function:
vector<string> subsequences(char ch, vector<string> v1, map<string, int> &m){
stringstream s1,s2;
string s,u;
char upper = toupper(ch);//for converting character to string
s1 << ch;
s1 >> s;
s2 << upper;
s2 >> u;if(v1.size()==0){
v1.push_back(“”);
v1.push_back(s);
v1.push_back(u);
m[“”]=1;
m[s]=1;
m[u]=1;
}
else{
vector<string> newlist;
for(auto it=v1.begin(); it!=v1.end(); it++){
newlist.push_back(s+(*it));
newlist.push_back(u+(*it));
m[u+(*it)]=1;
m[s+(*it)]=1;
}
v1.insert(v1.end(), newlist.begin(), newlist.end());
}
return v1;
}
4. Start traversing the string from it’s right end and find all the sub-sequences by adding one character of the string at each iteration to the sub-sequence.
for(int i=s.length()-1; i>=0; ){
v1= subsequences(s[i], v1, m1); i= i-1;
}
5. Printing the sub-sequences:
for(auto it=m1.begin(); it!=m1.end(); it++){
if(it->first !=””)cout<< it->first<<” “;
}
That’s it! We are done!
Hopefully, this article will clear all your doubts about the sub-sequences. Still, you can contact me in case, you are stuck somewhere. If you like the article and find it helpful, then please share it among your colleagues.
Your claps motivate me for writing more such articles and improving myself. :)
