CODEWITHSUNDEEP
javastringalgorithmoptimizationcomplexity-theory
user3011937
user3011937

Reputation: 261

Find longest substring formed with characters of other string

Given two strings:

str1 = "abcdefacbccbagfacbacer"
str2 = "abc"

I've to find the longest substring in str1 that is formed by the subset of characters of str2, in this case it would be - 7 (acbccba). What would be the approach to solve this in least complexity. First I thought of DP. But, I guess DP is really not required for this, as we have to search for substring, and not subsequence. Then I though of suffix tree. But that would require extra pre-processing time.

What would be the best way to do this? In fact, is this problem even suitable for a suffix tree, or DP?

Upvotes: 0

Views: 1729

Answers (4)

Subhash
Subhash

Reputation: 588

Tested code in Perl.

    use strict;
    use warnings;

    my $str1 = "abcdefacbccbagfacbacer";
    my $str2 = "abc";

    my @str1 = split ("", $str1);
    my @str2 = split ("", $str2);

    my @res = ();
    my $index = undef;
    my $max = 0;
    my @max_char = ();

    for(my $i = 0; $i < @str1; $i++){

        if ($str1[$i] =~ /[@str2]/){
            push (@res , $str1[$i]);
            next;
        }else{
            if(@res > $max){
                $max = @res;
                @max_char = @res;
                $index = $i;
            }
            @res = ();
        }
    }
    if(@res > $max){
        @max_char = @res;
        $index = $i;
    }

    $index = $index - $#max_char - 1;
    print "Longest substring = @max_char.  Starting from index $index";

Upvotes: 0

CloudyMarble
CloudyMarble

Reputation: 37566

There is actually only one way i can think of:

  1. Go on the chars of the string str1.
  2. Foreach char in str1 check if its in str2
  3. increase a counter (i) eachtime the current char in str1 was found in str2
  4. Once the char in str1 not part of str2 save the counter (i) value if its begger than the maxfound counter in maxfound which represents the longest found sequence and reset the (i) counter.

Upvotes: 0

Vincent van der Weele
Vincent van der Weele

Reputation: 13177

The easiest approach by far:

  1. Build a hashset of the second string.
  2. Loop over the first string and for each character, check if it is in the hashset. Keep track of the longest substring.

Running time: O(n+m) where n is the length of str1 and m is the length of str2.

(Non-tested) code:

Set<Character> set = new HashSet<>();
for (int i = 0; i < str2.length(); i++) {
    set.add(str2.charAt(i));
}

int longest = 0;
int current = 0;
int longestEnd = -1;
for (int i = 0; i < str1.length(); i++) {
    if (set.contains(str1.charAt(i)) {
        current++;
        if (current > longest) {
            longest = current;
            longestEnd = i + 1;
        }
    } else {
        current = 0;
    }
}

String result = "";
if (longest > 0) {
    result = str1.substr(longestEnd - longest, longestEnd);
}

Upvotes: 5

Leos Literak
Leos Literak

Reputation: 9474

Just an idea: wrap second string in [] and use Pattern's match method:

Pattern p = Pattern.compile("(["+str2+"])");
Matcher m = p.matcher(str1);
m.find();

and then m.group(1) shall find it.

Upvotes: 0

Related Questions