USACO Broken Necklace Help

[blackhawk_prince]

Hi, the question is You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:

1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.
Example

For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration will include the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.
PROGRAM NAME: beads
INPUT FORMAT
Line 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w
SAMPLE INPUT (file beads.in)

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
SAMPLE OUTPUT (file beads.out)

11

OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****
---------------------------------------------------------------------------------------------------------------------------------------------

Here is my code it works for most cases I tried but not :
77
rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr

Here is my code. Could someone please help me out. I cant get the code to work. Thanks

code:

/* ID: mashrur1 LANG: JAVA TASK: beads */ /*  *I will explain how I approched this problem. Make an array the best chain length then  *add the best two consecutive ones for the longest chain.  *  r r w w r b r b r r r r r b b b w w w      for this the count array should be  *  1 2 3 4 5 1 1 1 1 2 3 4 5 1 2 3 4 5 6             6 + 5 for the best total of 11  *  * But my code does not work for the case:  * 77  * rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr  *  */   import java.util.*; import java.io.*; public class beads {         private Scanner fileIn = new Scanner (new File ("gift.txt"));     private PrintWriter out = new PrintWriter (new BufferedWriter (new FileWriter ("dddd.txt")));     private int length;     private char [] necklace;     //count for how the chain is. It is alway at least one because the first bead will     //always count     private int currentCount = 1;     private int bestCount = 0;     private int [] count;     //length of the current chain     private int currentChainLength = 1;         public beads () throws IOException{         //length of the necklace         length = Integer.parseInt (fileIn.nextLine ());         necklace = fileIn.next ().toCharArray ();                 count = new int [length];         for (int i = 0 ; i  < length; i ++){             //initialize every element to be 1             count [i] = 1;         }                 //boolean is for if the necklace is made with only one colour         boolean multiColoured = false;         for (int i = 0; i < length; i++){             if (necklace [i] != necklace [0] || necklace [i] == 'w'){                 multiColoured = true;                 break;             }         }         //if only the necklace is multiColoured than find length         if (multiColoured == true){             breakLength (necklace);         } else { // else the break length is the necklace length             bestCount = length;         }     }         public void breakLength (char [] necklace){         //modify is true if a white bead is coloured blue or red         boolean modify;                 for (int i = 0; i < length; i++){             modify = false;             int j = i;                         //the start bead (i) is compared with all the beads to the right unitl             //one does not match             while (true){                 j ++;                 //when j counter reaches the end of the array start again at 0                 if (j >= length){                     j = 0;                     }                     //once j has reached the start bead break                     if (j == i){                         break;                     }                     //the bead matches with the start bead                     if (necklace [i] == necklace [j] || necklace [j] == 'w'){                         currentCount ++;                         currentChainLength ++;                     }                     else if (necklace [i] == 'w' && necklace [j] != 'w'){                         modify = true;                         //this is for the wbr case. the white could be matched with the blue bead                         //but not the red bead so the white bead must be painted a blue bead                         necklace [i] = necklace [j];                         currentCount ++;                         currentChainLength ++;                     } else {                         //the currentCount must be greater than the initial count of the                         //last two elements of the chain                         if (currentCount > count [j - 1] && currentCount - 1 > count [j - 2]){                             int tempCount = currentCount;                             int k = j - 1;                             //k is the last element of the chain                             while (tempCount > 0){                                 count [k] = tempCount;                                 tempCount --;                                 k --;                                 if (k < 0){                                     k = length - 1;                                 }                             }                             if (currentCount + count [k - 1] > bestCount){                                 System.out.println (currentCount + "  " + count [k - 1]);                                 bestCount = currentCount + count [k - 1];                             }                                }                                if (modify == true){                                     //is a white bead has been painted over then the bead must be                                     //painted white again for the next comparasion                                     necklace [i] = 'w';                                }                                currentCount = 1;                                break;                           }                                        }         }//end of for loop              }         public void write (){         //prints the results         System.out.println (Arrays.toString (necklace));         System.out.println (Arrays.toString (count));         System.out.println (bestCount);         //writes the bestCount in a text file         out.write (bestCount + "\r\n");         out.close();          System.exit(0);     }         public static void main(String[] args){         try {             beads b = new beads ();             b.write ();         } catch (Exception e){             System.out.println (e);         }     } }

[/i][/url]