310161: CF1791C. Prepend and Append

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Prepend and Append

题意翻译

对于一个字符串 $s$,你可以进行如下操作: - 在 $s$ 左侧添加字符 $\texttt1$,右侧添加字符 $\texttt0$;或者在 $s$ 左侧添加字符 $\texttt0$,右侧添加字符 $\texttt1$。 现给你一个字符串 $t$,求可以通过若干次操作变成字符串 $t$ 的字符串的最短长度。

题目描述

Timur initially had a binary string $ ^{\dagger} $ $ s $ (possibly of length $ 0 $ ). He performed the following operation several (possibly zero) times: - Add $ \texttt{0} $ to one end of the string and $ \texttt{1} $ to the other end of the string. For example, starting from the string $ \texttt{1011} $ , you can obtain either $ \color{red}{\texttt{0}}\texttt{1011}\color{red}{\texttt{1}} $ or $ \color{red}{\texttt{1}}\texttt{1011}\color{red}{\texttt{0}} $ . You are given Timur's final string. What is the length of the shortest possible string he could have started with? $ ^{\dagger} $ A binary string is a string (possibly the empty string) whose characters are either $ \texttt{0} $ or $ \texttt{1} $ .

输入输出格式

输入格式


The first line of the input contains an integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of testcases. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2000 $ ) — the length of Timur's final string. The second line of each test case contains a string $ s $ of length $ n $ consisting of characters $ \texttt{0} $ or $ \texttt{1} $ , denoting the final string.

输出格式


For each test case, output a single nonnegative integer — the shortest possible length of Timur's original string. Note that Timur's original string could have been empty, in which case you should output $ 0 $ .

输入输出样例

输入样例 #1

9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010

输出样例 #1

1
2
5
0
3
1
0
2
4

说明

In the first test case, the shortest possible string Timur started with is $ \texttt{0} $ , and he performed the following operation: $ \texttt{0} \to \color{red}{\texttt{1}}\texttt{0}\color{red}{\texttt{0}} $ . In the second test case, the shortest possible string Timur started with is $ \texttt{11} $ , and he performed the following operation: $ \texttt{11} \to \color{red}{\texttt{0}}\texttt{11}\color{red}{\texttt{1}} $ . In the third test case, the shortest possible string Timur started with is $ \texttt{10101} $ , and he didn't perform any operations. In the fourth test case, the shortest possible string Timur started with is the empty string (which we denote by $ \varepsilon $ ), and he performed the following operations: $ \varepsilon \to \color{red}{\texttt{1}}\texttt{}\color{red}{\texttt{0}} \to \color{red}{\texttt{0}}\texttt{10}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{0101}\color{red}{\texttt{0}} $ . In the fifth test case, the shortest possible string Timur started with is $ \texttt{101} $ , and he performed the following operations: $ \texttt{101} \to \color{red}{\texttt{0}}\texttt{101}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{01011}\color{red}{\texttt{0}} $ .

Input

题意翻译

对于一个字符串 $s$,你可以进行如下操作: - 在 $s$ 左侧添加字符 $\texttt1$,右侧添加字符 $\texttt0$;或者在 $s$ 左侧添加字符 $\texttt0$,右侧添加字符 $\texttt1$。 现给你一个字符串 $t$,求可以通过若干次操作变成字符串 $t$ 的字符串的最短长度。

Output

**题目大意:**

对于字符串s,可以执行以下操作:

- 在s的左侧添加字符`1`,在右侧添加字符`0`;或者在s的左侧添加字符`0`,在右侧添加字符`1`。

现给定一个字符串t,求可以通过若干次操作变成字符串t的字符串的最短长度。

**输入输出数据格式:**

**输入格式:**
- 第一行输入一个整数t(1≤t≤100),表示测试用例的数量。
- 每个测试用例的第一行输入一个整数n(1≤n≤2000),表示Timur最终字符串的长度。
- 每个测试用例的第二行输入一个长度为n的字符串s,由字符`0`或`1`组成,表示最终的字符串。

**输出格式:**
- 对于每个测试用例,输出一个非负整数,表示Timur原始字符串的最短可能长度。注意,Timur的原始字符串可能为空,在这种情况下应输出0。

**输入输出样例:**

**输入样例 #1:**
```
9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010
```

**输出样例 #1:**
```
1
2
5
0
3
1
0
2
4
```**题目大意:** 对于字符串s,可以执行以下操作: - 在s的左侧添加字符`1`,在右侧添加字符`0`;或者在s的左侧添加字符`0`,在右侧添加字符`1`。 现给定一个字符串t,求可以通过若干次操作变成字符串t的字符串的最短长度。 **输入输出数据格式:** **输入格式:** - 第一行输入一个整数t(1≤t≤100),表示测试用例的数量。 - 每个测试用例的第一行输入一个整数n(1≤n≤2000),表示Timur最终字符串的长度。 - 每个测试用例的第二行输入一个长度为n的字符串s,由字符`0`或`1`组成,表示最终的字符串。 **输出格式:** - 对于每个测试用例,输出一个非负整数,表示Timur原始字符串的最短可能长度。注意,Timur的原始字符串可能为空,在这种情况下应输出0。 **输入输出样例:** **输入样例 #1:** ``` 9 3 100 4 0111 5 10101 6 101010 7 1010110 1 1 2 10 2 11 10 1011011010 ``` **输出样例 #1:** ``` 1 2 5 0 3 1 0 2 4 ```

加入题单

上一题 下一题 算法标签: