Baba and Garlands

4.7

9 votes
Hard
Problem

Baba has a garland of N flowers some of which are Hibiscuses, others Lotuses, and others Roses, arranged at random (i.e. the flowers are of three types - Rose, Lotus, Hibiscus). Here are two examples for n=29:

            1 2                               1 2
        H L L H                           L H H L
      H         L                       L         H
     H           H                     L           H
    H             H                   R             H
   L               H                 R               R
  L                 L               H                 H
  L                 L               L                 L
  L                 L               H                 L
   H               H                 L               H
    L             H                   H             H
     L           H                     H           H
       H       H                         H       L
         H L H                             H H R
        Figure A                         Figure B
                    R rose
                    L lotus
                    H hibiscus

The flowers 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 L’s and H’s, where L represents a lotus and H represents a hibiscus, as follows: LHLHHHLLLHHHHHLHHLLHLLLLHHHHL.

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

Determine the point where the garland should be broken so that the most number of flowers can be collected.

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

But, Baba has a special fondness for Roses. When collecting flowers, a Rose that is encountered may be treated as either Lotus or Hibiscus (or may be added in either lotuses or hibiscuses).

Help Baba in determining the largest number of flowers that can be collected from a supplied garland.

INPUT:

The first line contains the number of test cases, T. Each of the next T lines contains a string of N characters, each of which is R, L or H.

OUTPUT:

For each test case, output a single line containing the maximum number of flowers that can be collected.

CONSTRAINTS:

  • 1<=T<=1000
  • 1<=length of string<=10000

Subtask 1 (30 points):

  • 1<=T<=10
  • 1<=length of string<=1000

Subtask 2 (70 points):

Original Constraints.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For Test Case 1:

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

                  Two garland copies joined here
                            v

RRRLLHRHLHLHHLHLHRHRRHLRHRHHL|RRRLLHRHLHLHHLHLHRHRRHLRHRHHL

                      ******|*****
                      HHHHHL|LLLLL  <-- assignments
                  5xH .....#|#####  6xL

                       5+6 = 11 total
Editor Image

?