4
\$\begingroup\$

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);
\$\endgroup\$
2
  • 1
    \$\begingroup\$ To check for anagrams, you typically want to sort the characters in each string, then see if the results are equal. \$\endgroup\$ Aug 19, 2016 at 15:45
  • \$\begingroup\$ As I said in the comment to @konijn's answer, I already tried sorting and it's actually slower because of all the conversions that you need to do. But maybe I implemented it wrong, so feel free to write your version of the perl code for that :-) \$\endgroup\$
    – ChatterOne
    Aug 19, 2016 at 23:04

4 Answers 4

2
\$\begingroup\$

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";
}
\$\endgroup\$
1
\$\begingroup\$

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);
\$\endgroup\$
1
  • \$\begingroup\$ Your accepted answer is something that you have written yourself. From a Code Review point of view it is no better than the original code that you posted in your question. Are you certain that this is the best advice that you have had? \$\endgroup\$
    – Borodin
    Aug 27, 2016 at 17:16
0
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ At least in JS, the quadratic solution did not pass. \$\endgroup\$
    – konijn
    Aug 20, 2016 at 12:39
  • \$\begingroup\$ @DarthGizka I don't understand what you mean saying that I can avoid generating all possible substrings. If I want the number of substrings that have the same character frequencies I need to know all the substrings, right? But maybe I'm missing something here, not sure. \$\endgroup\$
    – ChatterOne
    Aug 20, 2016 at 13:02
  • \$\begingroup\$ @konijn: your solution is O(N^2 N log N) = O(N^3 log N) and you said that it did pass... @ChatterOne: using frequency counts reduces the O(N log N) effort of konijn's sort().join() step to O(1), since you update only one character when extending a substring by one character. A byte or character is sufficient for a count slot since the maximum string length is so small (but keeping a sorted substring and inserting an incoming letter at the right position might work for a 'hobbled' scripting language, pushing effort into the engine: k = at(c, s); s = left(s, k) + c + substr(s, k + 1)). \$\endgroup\$
    – DarthGizka
    Aug 20, 2016 at 13:40
  • \$\begingroup\$ @ChatterOne: regarding a non-quadratic solution I can't help you at the moment since I have too many other things on my hands (my mind went completely blank when the admissibility of the quadratic solution became clear, erasing the solution that had begun to form and I don't have sufficient time for retracing my mental steps since I'm going offline). Have a look at suffix trees, at Rabin-Karp'ish things with an eye towards wildcarding, and at 'versioned'/'persistent' segment trees; none of these is necessarily part of the solution but going there you should find all that is needed. \$\endgroup\$
    – DarthGizka
    Aug 20, 2016 at 14:01
  • \$\begingroup\$ This keeps bothering me, to be sure, it is (N^2)/2 right? I only check remaining characters in the inner loop? \$\endgroup\$
    – konijn
    Aug 25, 2016 at 12:08
-1
\$\begingroup\$

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

  }
} 
\$\endgroup\$
5
  • 1
    \$\begingroup\$ This is an alternative implementation in an alternative language. Are you sure this qualifies as a review? \$\endgroup\$
    – Mast
    Aug 19, 2016 at 16:20
  • \$\begingroup\$ @Mast Absolutely, algorithms (sort substrings and keep track) are part of a codereview. Perhaps you skipped over the introductory paragraph? While succinct it tells the OP what is wrong, and what he should use instead. \$\endgroup\$
    – konijn
    Aug 19, 2016 at 16:48
  • \$\begingroup\$ @konijn Sorting was the first implementation that I had, the problem is that in perl you cannot directly access a string as if it were an array. What you have to do is split it to convert to an array, sort the array and the join it back so you can compare it to the other sorted string. It works but is much slower (benchmarked around 45% slower) than my current approach. \$\endgroup\$
    – ChatterOne
    Aug 19, 2016 at 23:02
  • \$\begingroup\$ This should be a bit slower for small strings, but much faster for large strings where you time out. \$\endgroup\$
    – konijn
    Aug 20, 2016 at 7:25
  • 1
    \$\begingroup\$ "but then again it's Perl" Tribalism is inappropriate here. It is as easy to write clear and well-structured code in Perl as in any other language, but even so it is beyond some programmers while others try to be "clever". That is not Perl's fault. Take a look at my Perl solution. \$\endgroup\$
    – Borodin
    Aug 24, 2016 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.