Question

How to count the number of substrings with exactly k distinct characters in PHP

Answer 1

function CountSubstringWithKDistinctChars($s, $k) {
    $count = 0;
    $size = strlen($s);
        
    for ($i = 0; $i < $size; $i++)  {
        $ch = $s[$i];
        $tmp = "" . $ch;
        $set = array();
        !in_array($ch, $set) ? array_unshift($set, $ch) : 0;
            
        for ($j = $i + 1; $j < $size; $j++) {
            $next_ch = $s[$j];
            !in_array($next_ch,$set) ? array_unshift($set, $next_ch) : 0;
            $tmp .= $next_ch;
            if (strlen($tmp) >= $k && count($set) == $k) {
                $count++;
            }
        }
    }
    return $count;
}
    

$str = "characters";
$k = 4;

echo "Number of substrings with exactly k distinct characters = ";
echo CountSubstringWithKDistinctChars($str, $k);




/*
run:

Number of substrings with exactly k distinct characters = 9

*/

 

70+ SQL courses for beginners and professionals