Re: [FWP] longest substring with unique characters

["Branden" <branden_clpm@hotmail.com>]

From: Casey R. Tweten wrote:
> Dan Chetlin brought up this challenge on #perl and I accepted.

Well, here's my version. It may look very much like C, but with the nature
of the test conditions, i don't believe it could be very different...


-------------------------- cut here -------------------------
#!/usr/bin/perl -w

while ($word = <DATA>) {
    chomp $word;

    $length     = length $word; # length of the word
    $max_length = 0;            # max substr length so far
    @results    = ( '' );       # longest substrs so far
    # NOTE: I included the empty string here so that
    # the program works with the empty string.
    # The empty string is the only substring of itself,
    # and should be returned as the only longest
    # substring with unique characters (it has no
    # characters, so it passes the test
    # $candidate !~ /(.).*\1/, which makes it
    # a valid substring for the problem).

    for ($i = 0; $i < $length - $max_length; $i++) {
        # try to find a substring of at least $max_length
        # characters beginning in position $i.
        # if $i >= $length - $max_length,
        # there cannot be one, so break out.

        for ($j = $length - $i; $j >= $max_length; $j--) {
            # try a substring beginning in position $i
            # with length $j. if $j < $max_length, it
            # doesn't matter if we find it, it's not what
            # we're looking for!

            $candidate = substr $word, $i, $j;
            if ($candidate !~ /(.).*\1/) {  # genial, Casey!
                # the candidate substring doesn't have
                # duplicate characters if i has more than
                # $max_length characters, clear the
                # @results so far and make a new $max_length.
                # Otherwise, just add it to results.
                if ($max_length < $j) {
                    $max_length = $j;
                    @results    = ();
                }
                push @results, $candidate;

                last;
                # well, strictly, last is not necessary,
                # since $max_length got updated and in
                # the next $j >= $max_length test it
                # would get out of the loop anyway.
                # but well, i just like it...
            }
        }
    }

    print "Longest substrings for word '$word':\n";
    print "* '$_'\n" for @results;
}

__DATA__
that
abcdefa
abcdabc
testing
this test

a
aabcdeaedcbaa
abcdefg
-------------------------- cut here -------------------------


Hope you enjoy,

Branden


==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe