This is what i did:
I run another query without pagination like this:
$newQuaryVars="&posts_per_page=99999999999999&post_type=post";
$posts = query_posts($query_string .$newQuaryVars);
$categoriesList = array();
$categoriesAmounts = array();
Then in the while have posts
i did the following:
while ( have_posts() ) : the_post();
$postCategories = get_the_category();
if($postCategories){
foreach($postCategories as $categoryInfo) {
$categoriesAmounts[$categoryInfo->term_id]['amount']++;
$categoriesList[$categoryInfo->term_id] = array(
'name' => $categoryInfo->name,
'url' => get_category_link( $categoryInfo->term_id ),
'amount' => $categoriesAmounts[$categoryInfo->term_id]['amount']
);
}
}
endwhile;
Now i basically have an array with categories name / url and the amount of posts that fit the search term within the that category.
after that i just array_multisort it and displayed it.
Hope that helps anyone out there.