递增字符串

问题描述

定义字符串完全由 ‘A’ 和 ‘B’组成，当然也可以全是’A’或全是’B’。如果字符串从前往后都是以字典序排列的，那么我们称之为严格递增字符串。

给出一个字符串s，允许修改字符串中的任意字符，即可以将任何的’A’修改成’B’，也可以将任何的’B’修改成’A’，

求可以使s满足严格递增的最小修改次数。

0 < s的长度 < 100000。

输入描述

输入一个字符串： “AABBA”

输出描述

输出：1

示例

示例1

输入

AABBA

输出

1

示例1

输入

AABAABBBA

输出

2

解题思路

1. 获取字符B首次出现索引位置，若不存在，则直接返回；
2. 获取字符A首次出现索引位置，若不存在，则直接返回；
3. 问题转化为两索引对应的字符串片段形成严格递增字符串问题；
4. 字符最小数为最大修改次数；
5. 定义一个指针，左边作为全为A，右边全为B，统计需要修改的次数，与最大修改次数比较获取最小值；

代码示例

/**
 * 获取成为严格递增字符串的最小修改次数
 * @param str 由 ‘A’ 和 ‘B’组成的字符串
 * @return 最小修改次数
 */
public int minModTimes(String str) {
          
   
    // 起始B字符位置
    int from = str.indexOf(B);
    if(from < 0) {
          
   
        return 0;
    }
    // 尾部A字符位置
    int to = str.lastIndexOf(A);
    if(from > to) {
          
   
        return 0;
    }

    // 右边A数量
    int r = 1;
    for (int i = from + 1; i < to; i++) {
          
   
        if(str.charAt(i) == A) {
          
   
            r++;
        }
    }
    // 左边B数量、最小修改数
    int l = 0, min = r;
    for(int i = from; i <= to; i++) {
          
   
        // 从索引位置开始将字符转成 A
        if(str.charAt(i) == B) {
          
   
            l++;
        } else {
          
   
            r--;
            min = Math.min(min, l + r);
        }
    }

    return min;
}