recursion problem

[Adam Frank]

i am trying to write a recursion which finds the longest sequence of string2 containting only letters from string1. for example if string1="abc" and string2="wacdbgabcf" the answer will be 4 as "acdb" is the longest substring of s2 containg only letters from string1.
to answer this question with recursion i decided first to find the number of letters of string1 in string 2 so wrote the following code

 
 // finds the longest substring of s2 containing chars only from s1
public static int maxString (String s1, String s2)
{   
        int n = s2.length();
        char c = s2.charAt(n-1);
        if ((s1.length()==0)) 
            return 0;
        if (n == 1)
        { 
            if (s1.indexOf(c) == -1) return 0;
            else return 1;
        }  
        if (s1.indexOf(c) == -1) return maxString(s1, s2.substring(n-1)); 
        else return maxString(s1, s2.substring(n-1)) + 1;
     }    

i think that it doesn't work because substring takes the right part of the string and i am searching from the left side but i don't have any idea how to fix it.

1. can you help me solve the problem?
2. am i going in the right way to solve the original problem or should i use a different way?
thanks.

[Ulf Dittmer]

I'd start by figuring out why the simple cases don't work, e.g.

"a" and "ab" --> 0

"a" and "ba" --> 2

when both should be 1.

[Adam Frank]

Ulf Dittmer wrote:I'd start by figuring out why the simple cases don't work, e.g.

"a" and "ab" --> 0

"a" and "ba" --> 2

when both should be 1.

i see that it checks the last char in the first time the recursion is called and also in the second time.
i have to check the leftest char so i changed c to be c = s2.charAt(0) it works for the cases you wrote but not for "a" and "aaa"

[Ankit Garg]

Adam Frank wrote:for example if string1="abc" and string2="wacdbgabcf" the answer will be 4 as "acdb" is the longest substring of s2 containg only letters from string1.
to answer this question with recursion i decided first to find the number of letters of string1 in string 2

I didn't understand this. string1 contains only abc then why do you think that the answer should be abcd??

[Adam Frank]

Ankit Garg wrote:

Adam Frank wrote:for example if string1="abc" and string2="wacdbgabcf" the answer will be 4 as "acdb" is the longest substring of s2 containg only letters from string1.
to answer this question with recursion i decided first to find the number of letters of string1 in string 2

I didn't understand this. string1 contains only abc then why do you think that the answer should be abcd??

sorry. my mistake. i had to write string1="abcd"

[Adam Frank]

i see that the recursion checks every time the first char but the recursion stops after two cycles.
can you help me fix it?

[Bert Bates]

intermediate

[Martijn Verburg]

I'm guessing that in your recursive calls that one of the 2 return statements below is being triggered.

#         if ((s1.length()==0))   
#             return 0;  
#         if (n == 1)  
#         {   
#             if (s1.indexOf(c) == -1) return 0;  
#             else return 1;  
#         }    

So you'll want to check, which one of those is being called and then how is the if clause being triggered (hint print out s1.length and s1.indexOf(c) as you go)

[Tony Docherty]

can you help me fix it?

I suggest you forget the coding side of the problem for the moment and write down a list of steps you need to complete to solve the problem. Then, once you have the algorithm sorted convert it to code. Trying write a straight to code solution for this sort of problem (and expecting to get it right first time) is beyond most people.