I have not solved algorithm problems in a while and thus, I have decided to take a look at the latest not difficult problems Codeforces.Com. I somehow liked the problem for Vasya And String as far as it seemed quite easy from a first view.
Actually, it was not that easy, but was not extremely difficult as well. Long story short, the problem is to generate the biggest substring consisting of equal letters considering the fact that we have a given number of possible changes. Thus, if we have aaabaabaaaa and we may change only once a string, the correct answer is aaabaaaaaaa. Thus, the second b should be changed. The tricky part is to realize how to do it. Once the solution was in my head, the coding was a piece of cake (one for-each loop and three conditions). But the piece of cake was playing hard to get…
The tricky part… So, my solution started with the following logic – does not matter whether I have a or b in the front, I would increment my answer by one until the minimum of as or bs reaches the allowed number of checks. Then, I would decrease the as and the bs until I can continue increasing the answer. The answer would never be decreased, because the reached one is a valid one.
Pretty much a lot of information, but if you are interested in the solution, you would get what I mean by looking at the code:
Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
using System; using System.Linq; class VasyaAndStroka { static void Main() { int[] int_line = Console.ReadLine().Split(new char[] { ' ' }).Select(int.Parse).ToArray(); int n = int_line[0]; int k = int_line[1]; string str_line = Console.ReadLine(); int ans = 0; int a = 0; int b = 0; int position = 0; foreach (var item in str_line) { if (item == 'a') { a++; } else { b++; } if (Math.Min(a,b) > k) { if (str_line[position] =='a') { a--; } else { b--; } position++; } else { ans++; } } Console.WriteLine(ans); } } |
Enjoy it! 😀