Subsequence of a string

Question

I have to write a program that takes string argument s and integer argument k and prints out all subsequences of s of length k. For example if I have

subSequence("abcd", 3);

the output should be

 abc abd acd bcd

I would like guidance. No code, please!

Thanks in advance.

Update:

I was thinking to use this pseudocode:

Start with an empty string
Append the first letter to the string 
  Append the second letter
    Append the third letter 
    Print the so-far build substring - base case
  Return the second letter
    Append the fourth letter
    Print the substring - base case
Return the first letter
   Append the third letter
     Append the fourth letter
     Print the substring - base case
   Return third letter
Append the second letter
   Append the third letter
     Append the fourth letter
     Print the substring - base case
   Return the third letter
Return the second letter
Append the third letter
   Append the fourth letter
Return third letter
Return fourth letter
Return third letter
Return second letter
Return first letter

The different indent means going deeper in the recursive calls.

(In response to Diego Sevilla):

Following your suggestion:

private String SSet = "";
private String subSequence(String s, int substr_length){
    if(k == 0){
       return SSet;
    }
    else{
    for(int i = 0; i < substr_length; i++){
        subString += s.charAt(i);
        subSequence(s.substring(i+1), k-1);
    }
   }
    return SSet;
}
}

Would `dcb` be a valid sequence or does it have to correspond to the given order of the string argument? — pjwilliams, Jul 13 '11 at 23:12
@Max: aba, abc, abd, bac, bad and so on. I guess the description of the problem is not very explanatory but this is what I have. — Nath, Jul 13 '11 at 23:23
Are you sure you are talking about sub sequences and not sub sets? A subsequence should only contain consecutive letters. — Gyan aka Gary Buyn, Jul 14 '11 at 00:21

score 1 · Answer 1 · answered Jul 13 '11 at 23:16

1

As you include "recursion" as a tag, I'll try to explain you the strategy for the solution. The recursive function should be a function like that you show:

subSequence(string, substr_length)

that actually returns a Set of (sub)-strings. Note how the problem could be divided in sub-problems that are apt to recursion. Each subSequence(string, substr_length) should:

Start with an empty substring set, that we call SSet.
Do a loop from 0 to the length of the string minus substr_length
In each loop position i, you take string[i] as the beginning character, and call recursively to subSequence(string[i+1..length], substr_length - 1) (here the .. imply an index range into the string, so you have to create the substring using these indices). That recursive call to subSequence will return all the strings of size substr_length -1. You have to prepend to all those substrings the character you selected (in this case string[i]), and add all of them to the SSet set.
Just return the constructed SSet. This one will contain all the substrings.

Of course, this process is highly optimizable (for example using dynamic programming storing all the substrings of length i), but you get the idea.

answered Jul 13 '11 at 23:16

Diego Sevilla

28,636
4
59
87

I tried to make some kind of pseudocode - please, see the update of my post. – Nath Jul 13 '11 at 23:28
@Nath, this could show how it will be executing things, but it is not a pseudo-code (for example, you don't show recursive calls). – Diego Sevilla Jul 13 '11 at 23:52
Yes, you are right. Since I was not able to make the pseudocode I decided to start from the end and going back to try to write the pseudocode based on this sequence of steps. – Nath Jul 14 '11 at 00:02
I apologize for the late response. I've updated my original post in order to try your suggestion but I am still missing details. Can you, please look at the update? – Nath Jul 14 '11 at 21:55
@Nath, in the code you show as my suggestion, SSet is actually a *set of strings*, not a String. It is actually the set of strings you're going to return at each step. Try thinking of SSet as a set and see if this makes more sense to you in the implementation. – Diego Sevilla Jul 15 '11 at 22:35

score 0 · Answer 2 · edited Jun 04 '20 at 11:55

string subSeqString() {
    string s1="hackerrank";
    string s="hhaacckkekraraannk";
    int k=0,c=0;
    int size=s1.size(); 
    for(int i=0;i<size;i++)
    {
        for(int j=k;j<s.size();j++)
        {
            if(s1[i]==s[j])
            {   
                c++;
                k++;
                break;
            }
            k++;
        }
    }
    if(c==size)
        return "YES";
    else
        return "NO";
}

score 0 · Answer 3 · answered Jul 14 '11 at 00:16

So, I see you want to implement a method: subSequence(s, n): Which returns a collection of all character character combinations from s of length n, such that ordering is preserved.

In the spirit of your desire to not provide you with code, I assume you would prefer no pseudo-code either. So, I will explain my suggested approach in a narrative fashion, leaving the translation to procedural code as an exercise-to-the-reader(TM).

Think of this problem where you are obtaining all combinations of character positions, which could be represented as an array of bits (a.k.a. flags). So where s="abcd" and n=3 (as in your example), all combinations could be represented as follows:

1110 = abc
1101 = abd
1011 = acd
0111 = bcd

Note, that we start with a bit-field where all characters are turned "on" and then shift the "off" bit over by 1. Things get interesting in an example where n < length(s) - 1. For example, say s="abcd" and n=2. Then we have:

1100 = ab
1001 = ad
1010 = ac
0110 = bc
0101 = bd
0011 = cd

The recursion comes into play when you analyze a sub set of the bit-fields. Hence, a recursive call would reduce the size of the bit-field and "bottom-out" where you have three flags:

100
010
001

The bulk of the work is a recursive approach to find all of the bit-fields. Once you have them, the positions of each bit can be used as an index in the the array of characters (that is s).

This should be sufficient to get you started on some pseudo-code!

after some of his comments, I realized he did care about the order of the substrings... so this solution is not what he wants... I edited my answer 'cause of that — woliveirajr, Jul 14 '11 at 02:31

score 0 · Answer 4 · answered Jul 14 '11 at 00:18

The problem is precisely this:

Given an ordered set S : {C0, C1, C2, ..., Cn}, derive all ordered subsets S', where each member of S' is a member of S, and relative order of {S':Cj, S':Cj+1} is equivalent to relative order {S:Ci, S:Ci+d} where S':Cj = S:Ci and S':Cj+1 = S:Ci+d. |S|>=|S'|.

Assume/assert size of set S, |S| is >= the size of the subset, |S'|
If |S| - |S'| = d, then you know each of the subsets S' begins with digit at Si, where 0 < i < d.

e.g given S:{a, b, d, c} and |S'| = 3

d = 1
S' sets begin with 'a' (S:0), and 'b' (S:1).

So we see the problem is actually to solve d lexically ordered permutations of length 3 of subsets of S.

@d=0: get l.o.permutations of length 3 for {a, b, c, d}
@d=1: get l.o.permutations of length 3 for {b, c, d}
@d=2: d > |S|-|S'|. STOP.

Subsequence of a string

4 Answers4