Interview programming question Get the

commonLongestSubSequence.php

<?php

/*
 * Intreview question
 * 
 * Build a function that returns common and longest sub-sequence of
 * the two strings.
 * 
 * For example,
 * AAAA,AA outputs: AA
 * AGGTAB, GXTXAYB outputs: GTAB
 * ABAZDC, BACBAD outputs: ABAD
**/

function commonLongestSubSequence(string $s1, string $s2) :string
{
    $longest = 0;
    $subSequence = "";
    $s1AsArray = str_split($s1);

    foreach ($s1AsArray as $index => $s1Char) {
        $tempS1 = substr($s1, $index);

        $ss = buildSubSequence($tempS1, $s2);
        if (empty($ss)) {
            continue;
        }

        $length = strlen($ss);

        if ($length > $longest) {
            $longest = $length;
            $subSequence = $ss;
        }
    }

    return $subSequence;
}

function buildSubSequence(string $s1, string $s2) :string
{
    $subSequence = "";

    foreach (str_split($s1) as $s1Char) {
        $pos = strpos($s2, $s1Char);

        if ($pos === false) {
            continue;
        }

        //Create a sub str and exclude
        $s2 = substr($s2, $pos + 1);

        $subSequence .= $s1Char;
     }

     return $subSequence;
}