Task — Subsequence

You are given two strings. Write a script to find out if one string is a subsequence of another. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.

Examples

Example 1
Input: $str1 = 'uvw', $str2 = 'bcudvew'
Output: true

Example 2
Input: $str1 = 'aec', $str2 = 'abcde'
Output: false

Example 3
Input: $str1 = 'sip', $str2 = 'javascript'
Output: true

Analysis

I'm not sure if it was intended, but the statement of the challenge suggests that we are to consider whether either string may be a subsequence of the other, and that is what I have provided for.

My solution relies on a constructed regular expression, matching $string1 against for example m|a.*b.*c|, where $string2 is 'abc'.

There a couple of potential flaws in my solution. One is that it assumes that string2 contains no characters which have a special meaning in a regular expression. It would be possible to use \Q and \E in the regular expressions if we cannot guarantee the absence of special characters.

The other is that regular expressions which contain variables are compiled at run time, and are noticeably slower than those explicitly defined at compile time.

If both strings are the same, my solution regards either one as a valid subsequence of the other, as I think is implied by 'can be none' in the challenge statement.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-04-07
use utf8;     # Week 316 - task 2 - Subsequence
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

subsequence('uvw', 'bcudvew');
subsequence('bcudvew', 'uvw');
subsequence('character', 'cat');
subsequence('scared', 'reduce');
subsequence('same', 'same');
subsequence('', 'challenge');

sub subsequence {
    
    my ($string1, $string2, $pattern1, $pattern2);
    
    # intitlaise
    ($string1, $string2) = @_;  
    say qq[\nInput:  \$string1 = '$string1', \$string2 = '$string2'];
    
    # create patterns (eg abc -> a.*b.*c.*)
    $pattern1 = join('.*', split('', $string1));
    $pattern2 = join('.*', split('', $string2));
    
    # see if they match
    if ($string1 =~ m|$pattern2|) {
        say qq[Output: yes - '$string2' is a subsequence of '$string1'];
    } elsif ($string2 =~ m|$pattern1|) {
        say qq[Output: yes - '$string1' is a subsequence of '$string2'];
    } else {
        say qq[Output: no - neither string is a subsequence of the other];
    }       
}

Output

Input:  $string1 = 'uvw', $string2 = 'bcudvew'
Output: yes - 'uvw' is a subsequence of 'bcudvew'

Input:  $string1 = 'bcudvew', $string2 = 'uvw'
Output: yes - 'uvw' is a subsequence of 'bcudvew'

Input:  $string1 = 'character', $string2 = 'cat'
Output: yes - 'cat' is a subsequence of 'character'

Input:  $string1 = 'scared', $string2 = 'reduce'
Output: no - neither string is a subsequence of the other

Input:  $string1 = 'same', $string2 = 'same'
Output: yes - 'same' is a subsequence of 'same'

Input:  $string1 = '', $string2 = 'challenge'
Output: yes - '' is a subsequence of 'challenge'