CF2103B Binary Typewriter

You are given a binary string $ s $ of length $ n $ and a typewriter with two buttons: 0 and 1. Initially, your finger is on the button 0. You can do the following two operations: 1. Press the button your finger is currently on. This will type out the character that is on the button. 2. Move your finger to the other button. If your finger is on button 0, move it to button 1, and vice versa. The cost of a binary string is defined as the minimum number of operations needed to type the entire string. Before typing, you may reverse at most one substring $ ^{\text{∗}} $ of $ s $ . More formally, you can choose two indices $ 1\le l\le r\le n $ , and reverse the substring $ s_{l\ldots r} $ , resulting in the new string $ s_1s_2\ldots s_{l-1}s_rs_{r-1}\ldots s_ls_{r+1}\ldots s_n $ . Your task is to find the minimum possible cost among all strings obtainable by performing at most one substring reversal on $ s $ . $ ^{\text{∗}} $ A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 2\cdot 10^5 $ ) — the length of the binary string $ s $ . The second line of each test case contains a binary string $ s_1s_2\ldots s_n $ ( $ s_i = \mathtt{0} $ or $ s_i = \mathtt{1} $ ) — the characters of the binary string $ s $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output the minimum cost of string $ s $ after performing at most one substring reversal.

In the first test case, we can choose not to reverse any substrings. We can do operation $ 1 $ three times to type 000. In the second test case, we can choose not to reverse any substrings. We can do operation $ 2 $ to move our finger to button 1. Then, we do operation $ 1 $ three times to type 111. In the third test case, we can choose not to reverse any substring. We can do operation $ 1 $ to type 0. Then, we do operation $ 2 $ to move our finger to button 1. Finally, we do operation $ 1 $ two times to type 11, resulting in the final string 011 using only $ 4 $ operations. In the fourth test case, we can reverse the substring $ s_{1\ldots 3} $ , resulting in the string 001. We can do operation $ 1 $ two times to type 00. Then we do operation $ 2 $ to move our finger to button 1. Finally, we do operation $ 1 $ once to type 1, resulting in the final string 001 using only $ 4 $ operations. In the fifth test case, we can reverse the substring $ s_{2\ldots 3} $ , resulting in the string 11001. The cost of the string is $ 8 $ as we can do the following sequence of operations: - Do operation $ 2 $ to move our finger to button 1. - Do operation $ 1 $ two times to type 11. - Do operation $ 2 $ to move our finger to button 0. - Do operation $ 1 $ two times to type 00. - Do operation $ 2 $ to move our finger to button 1. - Do operation $ 1 $ once to type 1. In the sixth test case, we can reverse the substring $ s_{5\ldots 17} $ , resulting in the string 1101111011001001000. It can be proven that the minimum number of operations needed to type the binary string is $ 29 $ .