常宁市网站建设,免费素材网png,宁德市地图,注册公司代理记账费用【问题描述】
给定一个由字符a和字符b组成的字符串#xff0c;可以删除若干字符#xff0c;使得剩下来的字符串满足前后段为a#xff0c;中间段为b#xff08;aaa....aaabbbb.....bbbbaaa.....aaa#xff09;,区段可以没有字符#xff08;ba,ab,b,aa都是合法的#xff…【问题描述】
给定一个由字符a和字符b组成的字符串可以删除若干字符使得剩下来的字符串满足前后段为a中间段为baaa....aaabbbb.....bbbbaaa.....aaa,区段可以没有字符ba,ab,b,aa都是合法的求最长剩下字符串的长度。
【输入形式】
输入为一行一个长度不超过5000的非空字符串字符串仅由字符a和字符b组成。
【输出形式】
输出为一个整数表示符合要求的最长剩下字符串长度
【样例输入1】
abba
【样例输出1】
4
【样例输入2】
bab
【样例输出2】
2
解题思路
解题方法前缀和双重循环遍历
题目理解 题目要求删除一些字符使得剩余的字符串形式为前面全是a中间全是b后面全是a的形式且要求剩余字符串尽可能长。
使用前缀和数组前缀和数组cnt用于快速计算任意区间内a的数量。cnt[i]表示原字符串中从头开始到位置i不包括i有多少个a。 cnt[i] cnt[i-1] (s.charAt(i-1) a ? 1 : 0);
计算最长字符数对于任意的分割点i和ji j可以将字符串分为三部分 第一部分[0, i)这部分应全为a即cnt[i]。 第二部分[i, j]这部分应全为b即j-i-(cnt[j] - cnt[i])。 第三部分(j, len]这部分应全为a即cnt[len] - cnt[j]。
找到最长字符数 通过双重循环遍历所有可能的i和j的组合计算出所有情况下的最长字符数取最大值maxLength。
输出maxLength。
Java代码
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);String s scanner.next();int len s.length();int[] cnt new int[len1];for (int i 1; i len; i) {cnt[i] cnt[i-1] (s.charAt(i-1) a ? 1 : 0);}int maxLength Integer.MIN_VALUE;for (int i 0; i len; i) {for (int j i; j len; j) {int Length cnt[i] (j-i-(cnt[j] - cnt[i])) (cnt[len] - cnt[j]);maxLength Math.max(Length, maxLength);}}System.out.println(maxLength);scanner.close();}
}
