Categories
General

Minimum Length Substrings

You are given two strings s and t. You can select any substring of string s and rearrange the characters of the selected substring. Determine the minimum length of the substring of s such that string t is a substring of the selected substring.Signature int minLengthSubstring(String s, String t)Inputs and t are non-empty strings that contain less than 1,000,000 characters eachOutput Return the minimum length of the substring of s. If it is not possible, return -1Examples = “dcbefebce” t = “fd” output = 5Explanation: Substring “dcbef” can be rearranged to “cfdeb”, “cefdb”, and so on. String t is a substring of “cfdeb”. Thus, the minimum length required is 5.

Facebook Solution

function minLengthSubstring($s, $t) {
  // Write your code here
       $s1 = str_split($s);
        $t1 = str_split($t);
        $hashmap = [];
        $countLengthSubstring = 1;
        $startingcounting = false;
        
        foreach ($t1 as $character) {
            $hashmap[$character] += 1;
        }
        
        foreach ($s1 as $character1) {
            if(array_key_exists($character1, $hashmap )) {
                if($startingcounting == false) {
                    $startingcounting = true;                
                }
                $hashmap[$character1] -= 1;
                if($hashmap[$character1] <= 0){
                    unset($hashmap[$character1]);       
                }
            }
            
            if(count($hashmap) == 0) {
                return $countLengthSubstring;
            }
            
            if($startingcounting) {
                $countLengthSubstring++;
            }
        }
        return -1;
  
}  

Clean

class solution {
    
    public function __construct() {}
    public function minLengthSubstring(string $s11, string $t11) 
    {
        $s1 = str_split($s11);
        $t1 = str_split($t11);
        $hashmap = [];
        $countLengthSubstring = 1;
        $startingcounting = false;
        
        foreach ($t1 as $character) {
            $hashmap[$character] += 1;
        }
        
        foreach ($s1 as $character1) {
            if(array_key_exists($character1, $hashmap )) {
                if($startingcounting == false) {
                    $startingcounting = true;                
                }
                $hashmap[$character1] -= 1;
                if($hashmap[$character1] <= 0){
                    unset($hashmap[$character1]);       
                }
            }
            
            if(count($hashmap) == 0) {
                return $countLengthSubstring;
            }
            
            if($startingcounting) {
                $countLengthSubstring++;
            }
        }
        return -1;
    }
}

// $s1 = "dcbefebce";
// $t1 = "fd";

$s1 = "bfbeadbcbcbfeaaeefcddcccbbbfaaafdbebedddf";
$t1 = "cbccfafebccdccebdd";

$solution = new Solution();
print $solution->minLengthSubstring($s1, $t1);

Leave a Reply