递增字符串

题目描述

定义字符串完全由 ‘A’ 和 ‘B’组成，当然也可以全是’A’或全是’B’。如果字符串从前往后都是以字典序排列的，那么我们称之为严格递增字符串。 给出一个字符串s，允许修改字符串中的任意字符，即可以将任何的’A’修改成’B’，也可以将任何的’B’修改成’A’，求可以使s满足严格递增的最小修改次数。0<s的长度<100000。

输入描述

输入一个字符串： “AABBA”

输出描述

输出：1 修改最后一位得到AABBB。

示例一

输入

AABBA

输出

1

参考解题 Java

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: Amos
 * @E-mail: amos@amoscloud.com
 * @Date: 2023/2/15
 * @Time: 11:24
 * @Description:
 */
public class Main0227 {
          
   
  public static void main(String[] args) {
          
   
    try (Scanner scanner = new Scanner(System.in)) {
          
   
      String line = scanner.next();
      System.out.println(solution(line));
    }
  }

  public static int solution(String str) {
          
   
    int n = str.length();
    int A = str.replaceAll("B", "").length();

    int dp = 0;
    int ans = A;

    for (int i = 0; i < n; i++) {
          
   
        if (str.charAt(i) == A) dp += 1;
        ans = Math.min(ans, check(i, dp, A - dp));
    }

    return ans;
  }
  /**
   * brand_LM_A : 当前位置左边A的个数(包含当前位置)
   * brand_R_A : 当前位置右边A的个数
   * brandIdx + 1 : 当前元素位置
   * brandIdx + 1 - brand_LM_A : 当前元素左边有几个B
   * 这个函数是计算当前位置 左边B的个数 + 右边A的个数 是想将左边B变为A，右边A变为B
   * 索引为brandIdx位置的元素，转为有序需要修改多少个字符
   */
  public static int check(int brandIdx, int brand_LM_A, int brand_R_A) {
          
   
    return brandIdx + 1 - brand_LM_A + brand_R_A;
  }
}