Subsequence

A subsequence of an array or string is a subset of its elements in the same order as the original sequence. The elements need not be contiguous.

For example, “ace” is a subsequence of “abcdce”. All elements of the subsequence appear in the same order in the original sequence.

Key properties of a subsequence:

Elements maintain their relative order from the original sequence
Elements need not be adjacent or contiguous in the original sequence
Multiple subsequences can exist within a sequence

Finding subsequences is useful for searching patterns and analyzing relationships between data.

Solution

Here is code to check if a subsequence exists:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
boolean isSubsequence(String s, String seq) {

  int index = 0;
  
  for (char ch : seq.toCharArray()) {
    index = s.indexOf(ch, index);   
    if(index == -1) return false;
    index++; 
  }

  return true;  
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
bool isSubsequence(string s, string seq) {
    
  int index = 0;
  
  for (char& ch: seq) {
    index = s.find(ch, index);
    if (index == string::npos) return false;
    index++;
  }
  
  return true;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def is_subsequence(s, seq):

  index = 0

  for ch in seq:
    index = s.find(ch, index)
    if index == -1:
      return False
    index += 1  
    
  return True

This iterates through the subsequence and checks if each element exists in order within the main sequence.

Subsequence matching can be customized via different matching logic as needed.

Description

A subsequence is a sequence that appears in the same relative order but not necessarily consecutively in the original sequence. In other words, from an array arr[0..n-1], you can form a subsequence by picking any set of elements in the same order they appear in arr. For instance, for the array [1, 2, 3], the subsequences could be [1], [2], [1, 2], [1, 3], [2, 3], and [1, 2, 3] among others.

Solution

Below are examples demonstrating how to find all the subsequences of a given array. We will use a recursive approach to generate the subsequences.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;

public class Subsequence {
    public static void generateSubsequences(int[] arr, int index, ArrayList<Integer> current) {
        if (index == arr.length) {
            System.out.println(current);
            return;
        }
        
        // Exclude current element
        generateSubsequences(arr, index + 1, current);

        // Include current element
        current.add(arr[index]);
        generateSubsequences(arr, index + 1, current);
        current.remove(current.size() - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        generateSubsequences(arr, 0, new ArrayList<>());
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;

void generateSubsequences(vector<int>& arr, int index, vector<int> current) {
    if (index == arr.size()) {
        for (int num : current) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }

    // Exclude current element
    generateSubsequences(arr, index + 1, current);

    // Include current element
    current.push_back(arr[index]);
    generateSubsequences(arr, index + 1, current);
}

int main() {
    vector<int> arr = {1, 2, 3};
    generateSubsequences(arr, 0, {});
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def generate_subsequences(arr, index, current):
    if index == len(arr):
        print(current)
        return

    # Exclude current element
    generate_subsequences(arr, index + 1, current)

    # Include current element
    generate_subsequences(arr, index + 1, current + [arr[index]])

if __name__ == "__main__":
    arr = [1, 2, 3]
    generate_subsequences(arr, 0, [])

Key Takeaways

We use recursion to explore both options for each element: either include it in the subsequence or exclude it.
The recursion base case is when we have made decisions for all elements in the array.
The logic remains consistent across Java, C++, and Python, differing only in syntax and data structures.