https://app.codility.com/cert/view/certXSSM37-5WPSRJECK7BXEV59/details/

 

An array of N words is given. Each word consists of small letters ('a' − 'z'). Our goal is to concatenate the words in such a way as to obtain a single word with the longest possible substring composed of one particular letter. Find the length of such a substring.

Write a function:

function solution($words);

that, given an array words containing N strings, returns the length of the longest substring of a word created as described above.

Examples:

1. Given N=3 and words=["aabb", "aaaa", "bbab"], your function should return 6. One of the best concatenations is words[1] + words[0] + words[2] = "aaaaaabbbbab". The longest substring is composed of letter 'a' and its length is 6.

2. Given N=3 and words=["xxbxx", "xbx", "x"], your function should return 4. One of the best concatenations is words[0] + words[2] + words[1] = "xxbxxxxbx". The longest substring is composed of letter 'x' and its length is 4.

3. Given N=4 and words=["dd", "bb", "cc", "dd"], your function should return 4. One of the best concatenations is words[0] + words[3] + words[1] + words[2] = "ddddbbcc". The longest substring is composed of letter 'd' and its length is 4.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..100,000];
  • all the words are non−empty and consist only of lowercase letters (az);
  • S denotes the sum of the lengths of words; S is an integer within the range [1..100,000].

function solution($words) {
    //echo "['".implode($words,"','")."']\n";
    
    $res=array();
    
    foreach($words as $index=>$w)
    {
        $s=strlen($w);
        $p=$w[0];
        
        $i=1;
        $current_start=0;
        $chars_count=1;
        $max_rep=0;
        $max_char=0;
        $first_repeat_len=0;
        $last_repeat_len=0;

        while($i<$s)
        {
            if($w[$i] != $p)
            {
                $len=$i-$current_start;
                if($len > $max_rep)
                {
                    $max_char=$w[$i-1];   
                    $max_rep=$len;
                }
                
                $current_start=$i;
                    
                if($chars_count == 1)
                    $first_repeat_len=$len;
                $chars_count++;
                    
                $p=$w[$i];
            }
            
            $i++;
        }
        
        $last_repeat_len=$s-$current_start;
        //echo $w[$s-1]." ".$index." ".$last_repeat_len."\n";
        
        $len=$s-$current_start;
        if($len > $max_rep)
        {
            //echo $index.": ".$max_char." ".$max_rep." ".$len."\n";
            $max_char=$w[$i-1];
            $max_rep=$len; 
        }
        
        if($chars_count == 1)
        {
            $p=$w[0];
            
            if(!isset($res[$p]))
                $res[$p]=array("in"=>0,"w"=>$s, "f0"=>array(-1,0), "f1"=>array(-1,0), "l0"=>array(-1,0), "l1"=>array(-1,0));
            else
                $res[$p]['w']+=$s;
                
            continue;
        }
        
        $p=$max_char;
        if(!isset($res[$p]))
            $res[$p]=array("in"=>$max_rep,"w"=>0, "f0"=>array(-1,0), "f1"=>array(-1,0), "l0"=>array(-1,0), "l1"=>array(-1,0));
        elsepre-wrap
            if($max_rep > $res[$p]["in"])
                $res[$p]["in"]=$max_rep;
                
        $p=$w[0];
        if(!isset($res[$p]))
            $res[$p]=array("in"=>0,"w"=>0, "f0"=>array($index,$first_repeat_len), "f1"=>array(-1,0), "l0"=>array(-1,0), "l1"=>array(-1,0));
        else
        {
            if($res[$p]["f0"][1]<$first_repeat_len)
            {
                $res[$p]["f1"]=$res[$p]["f0"];
                $res[$p]["f0"]=array($index, $first_repeat_len);
            }
            else
                if($res[$p]["f1"][1]<$first_repeat_len)
                    $res[$p]["f1"]=array($index, $first_repeat_len);
        }
        
        $p=$w[$s-1];
        if(!isset($res[$p]))
            $res[$p]=array("in"=>0, "w"=>0, "f0"=>array(-1,0), "f1"=>array(-1,0), "l0"=>array($index,$last_repeat_len), "l1"=>array(-1,0));
        else
        {
            if($res[$p]["l0"][1]<$last_repeat_len)
            {
                $res[$p]["l1"]=$res[$p]["l0"];
                $res[$p]["l0"]=array($index, $last_repeat_len);
            }
            else
                if($res[$p]["l1"][1]<$last_repeat_len)
                    $res[$p]["l1"]=array($index, $last_repeat_len);
        }
    }
    
    
    
    $max=0;
    
    foreach($res as $r)
    {
        $m=$r['w'];
        
        if($r['f0'][0]!=$r['l0'][0])
            $m+=$r['f0'][1]+$r['l0'][1];
        else
            $m+=max($r['f1'][1]+$r['l0'][1],$r['f0'][1]+$r['l1'][1]);
        
        $m=max($m, $r["in"]);
        
        if($m > $max)
            $max=$m;
    }
    
    return $max;
}