codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1082B.md (1728B)


      1 Source: https://codeforces.com/problemset/problem/1082/B
      2 
      3 B. Vova and Trophies
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Vova has won $n$ trophies in different competitions. Each trophy is either golden or silver. The trophies are arranged in a row.
     22 
     23 The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.
     24 
     25 Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.
     26 
     27 Input
     28 
     29 The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of trophies.
     30 
     31 The second line contains $n$ characters, each of them is either G or S. If the $i$-th character is G, then the $i$-th trophy is a golden one, otherwise it's a silver trophy.
     32 
     33 Output
     34 
     35 Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 10
     43 GGGSGGGSGG
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 7
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 4
     56 GGGG
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 4
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 3
     69 SSS
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 0
     76 ```
     77 
     78 Note
     79 
     80 In the first example Vova has to swap trophies with indices $4$ and $10$. Thus he will obtain the sequence "GGGGGGGSGS", the length of the longest subsegment of golden trophies is $7$.
     81 
     82 In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is $4$.
     83 
     84 In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than $0$.