It is not 'obvious' why the string should be bound by x's on both sides if you want the longest string. For n x's, the longest strings would seem to be

n = 
1 - x
2 - xx
3 - xxx.
4 - xxx.x....
5 - xxx.x.....x......
[download]

in other words, don't forget the trailing non-x caharacters to lengthen the string.

A regex to capture these strings is

my $regex = '\A' . ('[^x]*x' x $n) .  '[^x]*';
$foo =~ m{ ($regex) }xms;    # PBP orthodoxy :)
[download]

Update: With the problem redefined, the new regex should be retooled to use parsimonious quantifiers to find the shortest strings:

my $regex = '\A' . ('[^x]*?x' x $n);
[download]

Here I have also left off the last piece of the regex, as it is a noop.