力扣挑战赛第4天-No.1653使字符串平衡的最少删除次数

题目描述

给你一个字符串 s ，它仅包含字符 ‘a’ 和 ‘b’​​​​ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。我们称 s 平衡的 当不存在下标对 (i,j) 满足 i < j 且 s[i] = ‘b’ 同时 s[j]= ‘a’ 。

请你返回使 s 平衡 的 最少 删除次数。

示例：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

注意：

1 <= s.length <= 105
s[i] 要么是 'a' 要么是 'b'​ 。​

解法

分析可得，最终得到的字符串如果从某处开始分割，左侧应全为’a’,右侧应全为’b’，且这个字符串在所有符合的结果中是最长的。

对于字符串中的每一个字符，统计它前面出现的’b’和后面出现的’a’，最少的总和即为最少的删除次数（或者统计前面’a’的数量和后面’b’的数量，用字符串长度减去最大总和即为最少的删除次数）。

/**
 * @param {string} s
 * @return {number}
 */
const minimumDeletions = function (s) {
  let len = s.length;
  let aCountBeforeI = new Array(len).fill(0);
  let bCountAfterI = new Array(len).fill(0);
  if (s[0] === 'a') {
    aCountBeforeI[0]++;
  }
  if (s[len - 1] === 'b') {
    bCountAfterI[len - 1]++;
  }
  for (let i = 1; i < len; i++) {
    aCountBeforeI[i] = (s[i] === 'a') ? (aCountBeforeI[i - 1] + 1) : aCountBeforeI[i - 1];
  }
  for (let i = len - 2; i >= 0; i--) {
    bCountAfterI[i] = (s[i] === 'b') ? (bCountAfterI[i + 1] + 1) : bCountAfterI[i + 1];
  }
  let res = 0;
  for (let i = 0; i < len; i++) {
    res = Math.max(res, aCountBeforeI[i] + bCountAfterI[i]);
  }
  return len - res;
};

Donate