3

I got a task to implement algorithm that will find the longest possible substring from two given strings:

Input:

String s1="AAABBA";
String s2="ABAABBAAA";

so for that it would be AABBA. So i've implemented a method which returns a String, but then it got me - what if there are two substrings with equal, maximum possible length? That's when I decided to use LinkedList instead.

for example:

String s1="ABCIJK";
String s2="ABCDEFGHIJK";

So i am expecting here two substrings actually that are ABC and IJK respectively.

i've got the code:

import java.util.LinkedList;

public class SubstringFinder {

    public static LinkedList<String> findTheLongestSubstring(String s1, String s2)
    {
        LinkedList<String> allFound = new LinkedList<String>();
        String theLongest="";
        if(s1.length()>s2.length())
        {
            s1 = s1 + s2;
            s2 = s1.substring(0, (s1.length() - s2.length()));
            s1 = s1.substring(s2.length());
        }
                for(int j=0;j<s1.length();j++)
                {
                    for(int i=s1.length()-j; i>=0;i--)
                    {
                        if(s1.substring(j,j+i).length()>=theLongest.length() && s2.contains(s1.substring(j,j+i)))
                        {   
                            allFound.remove(theLongest);
                            theLongest=s1.substring(j,j+i);
                            allFound.add(theLongest);
                        }
                    }
                }

        return allFound;
    }

    public static void main(String[] args) {

        //String s1="ABCIJK";
        //String s2="ABCDEFGHIJK";
        String s1="AAABBA";
        String s2="ABAABBAAA";
        System.out.println(findTheLongestSubstring(s1,s2));

    } 
}   

And it returns me only "IJK" instead of [ABC, IJK]. when I comment

allFound.remove(theLongest)

it works OK in case of [ABC, IJK] but then it also adds [AAA] to the [AABBA] result, which is not expected. Is there any way to modify the condition so it adds only the longest strings to the list? or to remove all of the previous, shorter strings?

Thanks in advance

1 Answer 1

3

I have modified the method accordingly, please check my inline comment

public static LinkedList<String> findTheLongestSubstring(String s1, String s2)
    {
        LinkedList<String> allFound = new LinkedList<String>();
        String theLongest="";
        if(s1.length()>s2.length())
        {
            s1 = s1 + s2;
            s2 = s1.substring(0, (s1.length() - s2.length()));
            s1 = s1.substring(s2.length());
        }
        for(int j=0;j<s1.length();j++)
        {
            for(int i=s1.length()-j; i>=0;i--)
            {
                if(s1.substring(j,j+i).length()>=theLongest.length() && s2.contains(s1.substring(j,j+i)))
                {
                    theLongest = s1.substring(j, j+i);
                    // before adding any string check the length of existing string if it is less then remove it
                    if (allFound.size() > 0 && allFound.getFirst().length() < theLongest.length()) {
                        allFound.removeFirst();
                    }
                    allFound.add(theLongest);
                }
            }
        }

        return allFound;
    }
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.