4. Find Longest Repeated Pattern
public int findLongest(char c, String s, int length)
Given a String, find the longest sequence of matching characters in that String and return that int length. For instance, “aaabbccccccdde” has 6 c’s so the method would return 6 Call this method passing it the first character in the String, the rest of the String and 1, as in findLongest(‘a’, s, 1) length represents the longest matching sequence found so far, which is 1 because we found ‘a’ Base case: if length==0 or length==1 return the length of s Recursive cases: if c matches the 0th character of s, then we extend the sequence, return the value of the recursive call with c, the rest of s after the 0th character, and
length+1 else no match, return whichever is larger, length (the length we found of char c up to this point in s), or the value returned by recursively calling the method with the 0th character of s, the rest of s, and 1 as we are starting over
Example: “aaabbccccccdde” Call the method with ‘a’, “aabbccccccdde”, 1 First character matches, so call with ‘a’, “abbccccccdde”, 2 First character matches, so call with ‘a’, “bbccccccdde, 3 No match, so return max(3, call with ‘b’, “bccccccdde”, 1) First character matches, so call with ‘b’, “ccccccdde, 2 No match, so return max(2, call with ‘c’, “cccccdde”, 1) First character matches, so call with ‘c’, “ccccdde”, 2 … Eventually these calls return 6 (6 c’s found) Return max(2, 6) Return max(3, 6)
Run your program on the following inputs. “aabbbcddddddeefffghiii”, “19855aa00000cc24443bbb” , “33335557i322k555554p”, “2oo88rrrrr55ttyuuuuuuuuuuuuuuu44uuuuuuuuu4u444uuuuuuuuuuuuuuu”
This is what I have so far…
public static int findLongest(char c, String s, int length){
if (s.charAt(0) == s.charAt(1)) {
s = s.substring(1);
length ++;
System.out.println(s + length);
findLongest(c, s, length);
}
else if (s.charAt(0) != s.charAt(1)){
s = s.substring(1);
length = 1;
System.out.println(s + ” ” + length);
findLongest(c, s, length);
}
return length;
}
Thanks for any help!!
