{"problem":{"name":"B. Nikita and string","description":{"content":"One day Nikita found the string containing letters \"_a_\" and \"_b_\" only. Nikita thinks that string is beautiful if it can be cut into 3 strings (possibly empty) without changing the order of the lett","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF877B"},"statements":[{"statement_type":"Markdown","content":"One day Nikita found the string containing letters \"_a_\" and \"_b_\" only.\n\nNikita 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_\".\n\nNikita 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?\n\n## Input\n\nThe first line contains a non-empty string of length not greater than 5 000 containing only lowercase English letters \"_a_\" and \"_b_\".\n\n## Output\n\nPrint a single integer — the maximum possible size of beautiful string Nikita can get.\n\n[samples]\n\n## Note\n\nIt the first sample the string is already beautiful.\n\nIn the second sample he needs to delete one of \"_b_\" to make it beautiful.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"有一天，Nikita 找到了一个仅包含字母 \"_a_\" 和 \"_b_\" 的字符串。\n\nNikita 认为，如果一个字符串可以被切割成 #cf_span[3] 个子串（允许为空），且不改变字母的顺序，其中第 #cf_span[1] 个和第 #cf_span[3] 个子串仅包含字母 \"_a_\"，而第 #cf_span[2] 个子串仅包含字母 \"_b_\"，那么这个字符串就是美丽的。\n\nNikita 希望通过删除一些字符（可能不删除任何字符）来使字符串变得美丽，但不能改变剩余字符的顺序。他能得到的最长字符串的长度是多少？\n\n第一行包含一个非空字符串，长度不超过 #cf_span[5 000]，仅包含小写英文字母 \"_a_\" 和 \"_b_\"。\n\n请输出一个整数 —— Nikita 能得到的美丽字符串的最大可能长度。\n\n在第一个样例中，字符串已经是美丽的。\n\n在第二个样例中，他需要删除一个 \"_b_\" 才能使字符串变得美丽。\n\n## Input\n\n第一行包含一个非空字符串，长度不超过 #cf_span[5 000]，仅包含小写英文字母 \"_a_\" 和 \"_b_\"。 \n\n## Output\n\n请输出一个整数 —— Nikita 能得到的美丽字符串的最大可能长度。\n\n[samples]\n\n## Note\n\n在第一个样例中，字符串已经是美丽的。在第二个样例中，他需要删除一个 \"_b_\" 才能使字符串变得美丽。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\{a, b\\}^* $ be the input string of length $ n \\leq 5000 $.  \n\nA *beautiful string* is a subsequence of $ s $ that can be partitioned into three contiguous (in order) substrings $ w_1, w_2, w_3 $ such that:  \n- $ w_1 \\in a^* $,  \n- $ w_2 \\in b^* $,  \n- $ w_3 \\in a^* $.  \n\n**Objective**  \nFind the maximum length of a beautiful subsequence of $ s $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF877B","tags":["brute force","dp"],"sample_group":[["abba","4"],["bab","2"]],"created_at":"2026-03-03 11:00:39"}}