7730번 - Necklace 다국어

Frank the jeweller has to make an exclusive necklace for The Queen. The necklace will consist of silver, gold and bronze beads whose layout is exactly specified. All the gold beads are alike and can be used interchangeably, and so can the silver and bronze ones. Frank has prepared the beads for the job, and stuck them onto a single long pin. Now he is ready to assemble the necklace by taking the beads one by one off the pin, putting them onto the prepared string from either side, and finally joining the two ends of the string. (The join will be invisible after he is done, so it can be between any two adjacent beads on the final necklace.)

Unfortunately, the beads on the pin may not be in the same order as they will appear on the necklace. Therefore in the process of assembling the necklace, Frank will have to take beads off the pin and put them aside. However, Frank’s workshop is a great mess and he is worried he might lose some of the precious beads – and so he wants to minimize the maximum number of beads that will be lying aside at any moment in the process of assembling the necklace.

The first line of the input contains a single integer L (1 ≤ L ≤ 1000) – the number of beads in the necklace. The next line contains a string of L letters, each of which is G, S or B (standing for a gold, silver or bronze bead, respectively), that describes the final layout of the necklace. (Cut at any point and straightened out.) The third line of a test case contains a string of L letters describing the order of the beads on the pin. Frank can only remove the beads from the left end of the pin. You may assume that it is possible to assemble the necklace from the beads on the pin.

The output should consist of one line containing the minimum possible number of beads that Frank will have to store aside in the process of assembling the necklace.

Sample 1

Frank puts one silver bead on the string. Whichever place it will take in the final layout, both of its neighbours have to be gold, so the next three silver beads from the pin have to be stored aside. Then he can just put the remaining beads on the string, alternating gold ones from the pin and silver ones that have been set aside.

Sample 2

He can put the beads from the pin straight onto the string; golden ones from one end and silver ones from other end. He does not need to set any of them aside.