Slow anagrams detection

Question

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);

Answer 1

Here's my Perl solution to this problem, for comparison. It simply iterates through every non-empty substring of the original and sorts the characters of each one. The hash %count keeps track of the count of equivalent substrings

Once the counts have been established, the problem requires that the number of possible unordered pairs be calculated for each set of equivalent substrings

Because all of N items may be paired with N-1 others we have N (N-1) possible pairs. But a pair like N0 N1 is the same as N1 N0, so we must divide that expression by two, so the number of possible unordered pairs of N items is N (N-1) / 2. That expression appears literally in the code below

use strict;
use warnings 'all';

my ($n) = split ' ', <>;

while ( <> ) {

    my @s = /[a-z]/g;

    my %count;

    for my $i ( 0 .. $#s ) {
        for my $j ( $i .. $#s ) {
            my $ss = join '', sort @s[$i .. $j];
            ++$count{$ss};
        }
    }

    my $total = 0;

    for my $n ( values %count ) {
        $total += $n * ($n-1) / 2;
    }

    print $total, "\n";
}

Answer 2

Finally nailed it in Perl. In Python this same approach worked no problem, but clearly Perl (or at least the interpreter run on hackerrank) is much slower.

The "trick" is to extract all the substrings already in the form of an array, preferably already sorted, so that there is no need to do the loop another time inside of is_anagram.

Here is my code, admittedly not a beauty, but now it passes all tests.

use strict;
use warnings;

sub get_all_subarr {
    my ($input_string) = @_;

    my %results;

    foreach my $i (1..length($input_string)-1) {
        foreach my $j (0..length($input_string)-$i) {
            push @{$results{$i}}, [sort(split(//,substr($input_string, $j, $i)))];
        }
    }

    return \%results;
}

sub is_anagram {
    my ($arr_a, $arr_b) = @_;

    return 0 if (join('', @{$arr_a}) ne join('', @{$arr_b}));
    return 1;
}

my @results;

my $t = <STDIN>;
chomp $t;

while($t--) {
    my $input_string = <STDIN>;
    chomp $input_string;

    my $count = 0;
    my $strings_arr = get_all_subarr($input_string);
    foreach my $i (keys(%{$strings_arr})) {
        my $max_size = scalar(@{$strings_arr->{$i}})-1;
        foreach my $j (0..$max_size) {
            foreach my $k ($j+1..$max_size) {
                if (is_anagram($strings_arr->{$i}[$j], $strings_arr->{$i}[$k])) {
                    $count++;
                }
            }
        }
    }
    push @results, $count;
}

print join("\n", @results);

Answer 3

Rephrase the question as 'number of substrings that have exactly the same character frequencies' and take it from there...

That way you can avoid actually generating/processing all possible substrings, which is a surefire recipe for TLE (or at least it should be - don't know how good the testcases are at HackerRank).

P.S.: I looked and there are only 10 testcases with strings no longer than 100 characters, so even a simple quadratic* solution that enumerates all substrings should be sufficient - provided enough processing can be pushed into the engine, as always with script languages. The engine itself is implemented in a language that is actually suitable for programming, like C/C++, and hence all pre-fabbed functionality is several orders of magnitude faster than things done with interpreted script steps.

*) O(N^2 log N), actually, since the map insert is O(log N); however, from the POV of a scripting language the map insert is effectively O(1), compared to any manually programmed steps - that's why scripting languages get their time limits multiplied by such large factors

Answer 4

I will let someone else discuss the style, which looks terrible to me, but then again it's Perl ;) As Jerry Coffin mentioned, it's all about sorting and keeping track of sorted strings. Your techniques will not work.

This is my entry in JS that gets full marks, it should be obvious how this works

function processData(input) {

  lines = input.split('\n');
  lines.shift();

  for( line of lines  ){
    var map = {}, count = 0;

    for( inner = 0 ; inner < line.length;inner++ ){
      for( outer = inner ; outer < line.length ; outer++ )
       //Create a sorted substring, and keep track of the count
       //This was never meant for CodeReview, so yeah, comma chained statement to avoid curly braces ;]
       s = [...line.substring(inner,outer+1)].sort().join(), 
       map[s] = ( map[s] || 0 ) + 1;
    }
    for( a in map ){
      while(map[a]>1)
        count = count + --map[a];

    }
    console.log(count);

  }
}