Re: Unique-Character Substring

[dchetlin]

Well, heck, if we're going to do this re-posting in a different medium thing, here's what I had on FWP. Without benchmarking, I put my money on it being faster.

#!/usr/bin/perl -w
use strict;

local $" = ',';
while (<DATA>) {
  chomp;
  my @chars = split //;
  my $index = -1;
  my %seen = ();
  my $answer = [""];
  while (++$index < @chars) {
    if (exists $seen{$chars[$index]}) {
      answer_set(\%seen, $answer);
      $index = $seen{$chars[$index]};
      %seen = ();
    } else {
      $seen{$chars[$index]} = $index;
    }
  }
  answer_set(\%seen, $answer);
  print "$_: @$answer\n";
}

sub answer_set {
  my $seen = shift;
  goto 'JUMP_' . ((keys %$seen <=> length $_[0][0]) + 1);
  JUMP_0:
    return;
  JUMP_2:
    $_[0] = [];
  JUMP_1:
    push @{$_[0]},
      join "", sort { $seen->{$a} <=> $seen->{$b} } keys %$seen;
    return;
}
__DATA__
mississippi
abcbef
adbcbef
that
abcdefa
abcdabc
testing
this test
abcdefg

-dlc

[salvadors]

Without benchmarking, I put my money on it being faster.

I'd hold on to your money, if I were you. On a short string mine is about 4 times faster. On a longer string it's about 10 times faster...

Tony