题目：A5

思路：

1. 对于字符串中的每一个位置，如果前面有大于等于3个'A'，且后面有大于等于2个'5'，那么需要考虑将前面的'A'修改到2个，或者将后面的'5'修改到1个。
2. 答案一：只修改前面的'A'，从前往后遍历字符串，如果该位置存在不合法的子序列，那么记录通过修改前面的'A'将当前位置变为合法的最小修改数。答案为所有位置的最小修改数的最大值。
3. 答案二：只修改后面'5'，同答案一的做法。
4. 答案三：修改前面x个'A'和后面y个'5'，是当前字符串不存在子序列'AAA55'。将答案一中遍历时产生的最小修改数用数组记录。按只修改前面的最小修改数从小到大排序，并用一个数组记录排序后的数组的只修改后面的后缀最大值。从左往右遍历数组，答案就是当前只修改前面的修改数+只修改后面的最大值。
5. 最终答案是三者中的最小值。

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	static int mod=1_000_000_007;
	public static void main(String[] args) throws IOException {
		String s=br.readLine();
		int t=Integer.parseInt(s);
		for(;t>0;t--) {
			s=br.readLine();
			char[] c=s.toCharArray();
			int n=c.length;
			//记录在遍历字符串的过程中如果某一位置存在目标子序列，只修改前或后使目标字符串消失的最小值
			//0为只修改前面，1为只修改后面
			int[][] dp=new int[n][2];
			//c5记录字符串中5的个数，ca记录字符串中A的个数
			int c5=0,ca=0;
			for(int i=n-1;i>=0;i--) {
				if(c[i]=='5') {
					c5++;
				}
			}
			//a是只修改前面的最大值，b是只修改后面的最大值
			int a=-1,b=-1;
			for(int i=0;i<n;i++) {
				if(ca>2&&c5>1) {
					dp[i][0]=ca-2;
					dp[i][1]=c5-1;
				}
				if(c[i]=='A') {
					ca++;
				}
				else {
					c5--;
				}
				a=Math.max(a, dp[i][0]);
				b=Math.max(b, dp[i][1]);
			}
			int ans=Math.min(a, b);
			//对只修改前面的修改数排序
			Arrays.sort(dp, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					if(o1[0]>o2[0]) {
						return 1;
					}
					return -1;
				}
			});
			//记录后面只修改后面的最大修改数
			int[] cm=new int[n];
			cm[n-1]=dp[n-1][1];
			for(int i=n-2;i>=0;i--) {
				cm[i]=Math.max(dp[i][1], cm[i+1]);
			}
			for(int i=0;i<n-1;i++) {
				ans=Math.min(ans, dp[i][0]+cm[i+1]);
			}
			pw.println(ans);
		}
		pw.flush();
	}
}