in reply to Unique-Character Substring

I found your description rather confusing. You are not interested in substrings, rather in substrings that do not find repeated characters. (I take it that UCS means Unique Character Substrings?) For comparison here is another approach based on recursive splits of the string rather than repeated calls to index. I have no idea how it compares for efficiency. 
sub tilly_UCS {
  my $str = shift;
  # Try all cuts.  Those that don't fall in 2 are repeats
  foreach my $char (split //, $str) {
    my @cut = split /\Q$char\E/, $str, -1;
    if (2 != @cut) {
      my @rejoined = map "$cut[$_-1]$char$cut[$_]", 1..$#cut;
      @rejoined = sort {length $b <=> $a} @rejoined;
      my @unique = tilly_UCS(shift @rejoined);
      foreach my $str (@rejoined) {
        if (length($str) < length($unique[0])) {
          last; # Avoid useless work, cannot improve
        }
        my @found = tilly_UCS($str);
        if (length($found[0]) > length($unique[0])) {
          @unique = @found;
        }
        elsif (length($found[0]) == length($unique[0])) {
          push @unique, @found;
        }
      }
      return @unique;
    }
  }
  # No repeats
  return $str;
}

[download]
BTW those that don't know what the third argument to shift did should look it up. You will avoid a commmon misunderstanding that can lead to bugs.

Replies are listed 'Best First'.
Re: Re (tilly) 1: Unique-Character Substring
by salvadors (Pilgrim) on Jan 20, 2001 at 19:40 UTC

    This doesn't do the same as the original. When fed "The quick brown fox jumps over the lazy dog" it returns "quick brown quick brown quick brown quick brown" rather than the "quick brown" of the original.

    I also found it strange that you return @unique under one condition, and $str under another...

    And I assume you meant the third argument to split rather than shift?

    Tony

[reply]
      Oops, on both counts. I meant split, not shift.

      As for the different returns, in one case I verified that it was a unique string and so return the original, in the other I verified it was not and returned the substrings in it. However I don't keep context about locations in the original string, so I cannot tell whether a duplicate is because I found the same string through two paths. In your example through cutting on 'h' then 'e' I get to ' quick brown fox jumped ov' no matter which way I split on 'h' first.

      That is fixable, but not easily.

[reply]

In Section Craft