This is my code for this question on hackerrank. The idea is to find the amount of substrings of a given word that are anagrams of each other.
The code works fine, but it times out with longer strings. I've downloaded the test cases to make sure the result is correct and it is, it just takes too long. I can do this in C and pass all tests, but I was wondering if there is a faster alternative in Perl.
I also tried using numbers, i.e. multiplying the ord()-97
of the characters in the two substrings, and then doing a single check on the number, to see if they are anagrams of each other.
That is much faster, but only works on small strings because it overflows quickly.
In this specific case, I'm not really that concerned about style, as much as performance. How can this be improved?
use strict;
use warnings;
use Data::Dumper;
sub get_all_substr {
my ($input_string) = @_;
my @results;
push @results, $input_string =~ /(?=(.{$_}))/g for 1 .. length($input_string);
return \@results;
}
sub is_anagram {
my ($string_a, $string_b) = @_;
my $len_a = length($string_a);
return 0 if (length($string_b) != $len_a);
my %vec_a;
my %vec_b;
foreach my $i (0..$len_a-1) {
$vec_a{substr($string_a, $i, 1)}++;
$vec_b{substr($string_b, $i, 1)}++;
}
return 0 if (scalar(keys(%vec_a)) != scalar(keys(%vec_b)));
foreach my $key (keys(%vec_a)) {
if (!defined($vec_b{$key}) || ($vec_a{$key} != $vec_b{$key})) {
return 0;
}
}
return 1;
}
my @results;
my $t = <STDIN>;
chomp $t;
while($t--) {
my $input_string = <STDIN>;
chomp $input_string;
my $count = 0;
my $strings;
$strings = get_all_substr($input_string);
my $max_size = scalar(@{$strings})-1;
foreach my $i (0..$max_size) {
foreach my $k ($i+1..$max_size) {
if (is_anagram($strings->[$k], $strings->[$i])) {
$count++;
}
}
}
push @results, $count;
}
print join("\n", @results);