recursion problem

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.

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.

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"

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??

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"

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

intermediate

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)

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.