877B.md (1140B)
1 Source: https://codeforces.com/problemset/problem/877/B 2 3 B. Nikita and string 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 One day Nikita found the string containing letters "a" and "b" only. 22 23 Nikita thinks that string is beautiful if it can be cut into 3 strings (possibly empty) without changing the order of the letters, where the 1-st and the 3-rd one contain only letters "a" and the 2-nd contains only letters "b". 24 25 Nikita wants to make the string beautiful by removing some (possibly none) of its characters, but without changing their order. What is the maximum length of the string he can get? 26 27 Input 28 29 The first line contains a non-empty string of length not greater than 5 000 containing only lowercase English letters "a" and "b". 30 31 Output 32 33 Print a single integer — the maximum possible size of beautiful string Nikita can get. 34 35 Examples 36 37 Input 38 39 ``` 40 abba 41 ``` 42 43 Output 44 45 ``` 46 4 47 ``` 48 49 Input 50 51 ``` 52 bab 53 ``` 54 55 Output 56 57 ``` 58 2 59 ``` 60 61 Note 62 63 It the first sample the string is already beautiful. 64 65 In the second sample he needs to delete one of "b" to make it beautiful.