Re: Longest possible run of a single character

[TedPride]

A linear solution, which will work fast for any size string:

use strict;
use warnings;

my ($c, $maxn, $n, $maxc, $str) = ('', 0);
$str = join '', <DATA>;

for (0..(length($str)-1)) {
    $_ = substr($str, $_, 1);
    if ($_ ne $c) {
        $n = 1;
        $c = $_;
    }
    else {
        $n++;
        if ($n > $maxn) {
            $maxn = $n;
            $maxc = $c;
        }
    }
}

print $maxc x $maxn;

__DATA__
ABDBACCBBBCBDDBCDCBCCDBABCBABBBBBADACDABACC

[BrowserUk]

Never under estimate the performance of the regex engine.

#! perl -slw
use strict;
use List::Util qw[ reduce ];
use Benchmark qw[ cmpthese ];

our $str;

sub TedP {
    my ($c, $maxn, $n, $maxc) = ('', 0);

    for (0..(length($str)-1)) {
        $_ = substr($str, $_, 1);
        if ($_ ne $c) {
            $n = 1;
            $c = $_;
        }
        else {
            $n++;
            if ($n > $maxn) {
                $maxn = $n;
                $maxc = $c;
            }
        }
    }
    return $maxc x $maxn;
}

sub regex {
    return reduce{
        length $a > length $b ? $a : $b
    } $str =~ m[((.)\2+)]g;
}

for my $n (  1 .. 6 ) {
    $str = join'', map{chr(65+rand(26)) x int(rand 20) } 1 .. 10**$n;
    print "\nString length ", length $str;
#    print regex();
#    print TedP();
    cmpthese -1, { TedP=> \&TedP, Regex=> \&regex };
}

__END__
C:\test>551038

String length 89
         Rate  TedP Regex
TedP  12429/s    --  -50%
Regex 24837/s  100%    --

String length 939
        Rate  TedP Regex
TedP  1265/s    --  -51%
Regex 2598/s  105%    --

String length 9741
       Rate  TedP Regex
TedP  126/s    --  -48%
Regex 242/s   92%    --

String length 94791
        Rate  TedP Regex
TedP  12.6/s    --  -43%
Regex 22.3/s   77%    --

String length 949396
            (warning: too few iterations for a reliable count)

            (warning: too few iterations for a reliable count)

        Rate  TedP Regex
TedP  1.29/s    --  -40%
Regex 2.16/s   67%    --

String length 9496562
            (warning: too few iterations for a reliable count)

            (warning: too few iterations for a reliable count)

      s/iter  TedP Regex
TedP    7.72    --  -39%
Regex   4.74   63%    --