Reducing a 2D array to its longest unique series that aren't contained within any other
Bug

Try the following input:

$catLists = array( 
                    0 =&gt; array('sml', 'med', 'lrg', 'xlg', 'xxl'),
                    1 =&gt; array('smlmed', 'lrg', '', '', ''));


I think that this will produce just one row of output, although it should produce two (these arrays are distinct).  To avoid this, you should check the arrays after finding matching strings or use some character that would never appear in the strings to join them.  If you change the join character, note that you may have to trim out the empty portion before generating the string.  

For example, the colon (:) would work in your example:

$stringified = ':' . implode(':', $catList) . ':';


but would produce strings like :big::::: when you probably just want :big:.  

Avoid unnecessary variables


            $contained = false;
            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) $contained = true;
            }
            if (!$contained) {
                $catList_strings[] = $stringified;
                $reduced_catLists[] = array_filter($catList);
            }



You can just say 

            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) {
                    $catList_strings[] = $stringified;
                    $reduced_catLists[] = array_filter($catList);
                    break;
                }
            }


This is also more performant, as it stops as soon as it finds a match.  The original code tried to generate more.  

Consider using an associative array

You can make this more direct.  Something like:

function array_contains($base, $candidate, $start = 0) {
    if (count($base) &lt; count($candidate) - $start) {
        return false;
    }

    foreach ($base as $v) {
        if ($v != $candidate[$start]) {
            return false;
        }
    }

    return true;
}

$indexesOf = array();
foreach ($catLists as $i =&gt; $catList) {
    $trimmedList = array_filter($catList);
    foreach ($trimmedList as $j =&gt; $cat) {
        if (isset($indexesOf[$cat]) {
            if (0 == $j) {
                foreach ($indexesOf[$cat] as $index =&gt; $start ) {
                    if (array_contains($catList, $catLists[$index], $start)) {
                        break 2;
                    }
                }
            }
        } else {
            $indexesOf[$cat] = array();
        }

        $indexesOf[$cat][$i] = $j;
        $reducedCatLists[] = $trimmedList;
    }
}


This uses a dictionary lookup to search for arrays that could potentially contain the current one.  

Bug 2

Perhaps this isn't an issue, but the array order matters here.  You only check arrays that you've already seen.  I do this as well.  Not sure how much it matters, but 

$catLists = array( 
                    0 =&gt; array('500ml', '750ml', '', '', ''),
                    1 =&gt; array('300ml', '500ml', '750ml', '1L', ''));


and 

$catLists = array( 
                    0 =&gt; array('300ml', '500ml', '750ml', '1L', ''),
                    1 =&gt; array('500ml', '750ml', '', '', ''));


will return different results.  

If you want to get the same result from both inputs, then you have to loop through the array twice.  The first time, you build the lookup array.  The second time, you build the reduced list.  

Test

If you have historically accurate values for $catList run a test where you time how long it takes to process either way.  

Note that if it only changes weekly, it may be reasonable to save $reducedCatList when it first appears.  That would be unlikely to cause significant load to the server, as you can choose to do it at a time when most legitimate users don't use the server.  Something like 3 AM is great, but even a time like 3 PM might work.  I don't know what patterns your customers follow.