2696. 删除子串后的字符串最小长度

给你一个仅由大写英文字符组成的字符串 s 。

你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除任一个 "AB" 或 "CD" 子字符串。

通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的最小可能长度。

注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。

示例

示例 1

输入：s = "ABFCACDB"
输出：2
解释：你可以执行下述操作：
从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。
从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。
从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。
最终字符串的长度为 2 。可以证明 2 是可获得的最小长度。

示例 2

输入：s = "ACBBD"
输出：5

解释：无法执行操作，字符串长度不变。

代码

javascripttypescript

javascript

// 2696. 删除子串后的字符串最小长度
// https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/

// 只去除 AB 或 CD
export function minimumStringLengthAfterRemovingABOrCDSubstrings(str) {
  while(str.indexOf('AB') > -1 || str.indexOf('CD') > -1) {
    str = str.replace('AB', '').replace('CD', '')
  }
  return str.length
}

// 去除 AB / CD / BC 等所有的两个子串
export function minimumStringLengthAfterRemovingSubstrings(str) {
  const strCharCode = str.split('').map(x => x.charCodeAt(0))

  const getSubstringPosition = () => {
    let subIndex = -1
    for(let i = 0, len = strCharCode.length; i < len - 1; i++) {
      if (strCharCode[i + 1] - strCharCode[i] === 1) {
        subIndex = i
        break
      }
    }
    return subIndex
  }
  let getSubstringIndex = getSubstringPosition()
  while(getSubstringIndex > -1) {
    strCharCode.splice(getSubstringIndex, 2)
    getSubstringIndex = getSubstringPosition()
  }
  return strCharCode.length
}

// 去除 AB / CD / BC 等所有的两个子串，栈实现
export function minimumStringLengthAfterRemovingSubstringsStack(str) {
  const strCharCode = str.split('').map(x => x.charCodeAt(0))
  const resList = []
  strCharCode.forEach(item => {
    if (item - resList[resList.length - 1] === 1) {
      resList.pop()
    } else {
      resList.push(item)
    }
  });
  return resList.length
}

typescript

// 2696. 删除子串后的字符串最小长度
// https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/

// 只去除 AB 或 CD
export function minimumStringLengthAfterRemovingABOrCDSubstrings(str: string): number {
  while(str.indexOf('AB') > -1 || str.indexOf('CD') > -1) {
    str = str.replace('AB', '').replace('CD', '')
  }
  return str.length
}

// 去除 AB / CD / BC 等所有的两个子串
export function minimumStringLengthAfterRemovingSubstrings(str: string): number {
  const strCharCode = str.split('').map(x => x.charCodeAt(0))

  const getSubstringPosition = () => {
    let subIndex = -1
    for(let i = 0, len = strCharCode.length; i < len - 1; i++) {
      if (strCharCode[i + 1] - strCharCode[i] === 1) {
        subIndex = i
        break
      }
    }
    return subIndex
  }
  while(getSubstringPosition() > -1) {
    strCharCode.splice(getSubstringPosition(), 2)
  }
  return strCharCode.length
}

// 去除 AB / CD / BC 等所有的两个子串，栈实现
export function minimumStringLengthAfterRemovingSubstringsStack(str: string): number {
  const strCharCode = str.split('').map(x => x.charCodeAt(0))
  const resList: number[] = []
  strCharCode.forEach(item => {
    if (item - resList[resList.length - 1] === 1) {
      resList.pop()
    } else {
      resList.push(item)
    }
  });
  return resList.length
}

测试代码

test

import { expect, test } from 'vitest'
import {
  minimumStringLengthAfterRemovingABOrCDSubstrings,
  minimumStringLengthAfterRemovingSubstrings,
  minimumStringLengthAfterRemovingSubstringsStack
} from './typescript.js'
import {
  minimumStringLengthAfterRemovingABOrCDSubstrings as minimumStringLengthAfterRemovingABOrCDSubstringsJs,
  minimumStringLengthAfterRemovingSubstrings as minimumStringLengthAfterRemovingSubstringsJs,
  minimumStringLengthAfterRemovingSubstringsStack as minimumStringLengthAfterRemovingSubstringsStackJs
} from './javascript.js'

// 只去除 AB 或 CD
test(`'ABFCACDB' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingABOrCDSubstrings('ABFCACDB')).toBe(2)
})

test(`'ACBBD' toBe 5`, () => {
  expect(minimumStringLengthAfterRemovingABOrCDSubstrings('ACBBD')).toBe(5)
})

test(`'ABFCJACDBK' toBe 4`, () => {
  expect(minimumStringLengthAfterRemovingABOrCDSubstrings('ABFCJACDBK')).toBe(4)
})

test(`'ABFCACDB' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingABOrCDSubstringsJs('ABFCACDB')).toBe(2)
})

test(`'ACBBD' toBe 5`, () => {
  expect(minimumStringLengthAfterRemovingABOrCDSubstringsJs('ACBBD')).toBe(5)
})

test(`'ABFCJACDBK' toBe 4`, () => {
  expect(minimumStringLengthAfterRemovingABOrCDSubstringsJs('ABFCJACDBK')).toBe(4)
})

// 去除 AB / CD / BC 等所有的两个子串
test(`'ABFCACDB' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstrings('ABFCACDB')).toBe(2)
})

test(`'ACBBD' toBe 5`, () => {
  expect(minimumStringLengthAfterRemovingSubstrings('ACBBD')).toBe(5)
})

test(`'ABFCJACDBK' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstrings('ABFCJACDBK')).toBe(2)
})

test(`'ABFCACDB' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsJs('ABFCACDB')).toBe(2)
})

test(`'ACBBD' toBe 5`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsJs('ACBBD')).toBe(5)
})

test(`'ABFCJACDBK' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsJs('ABFCJACDBK')).toBe(2)
})

// 去除 AB / CD / BC 等所有的两个子串，栈实现
test(`'ABFCACDB' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsStack('ABFCACDB')).toBe(2)
})

test(`'ACBBD' toBe 5`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsStack('ACBBD')).toBe(5)
})

test(`'ABFCJACDBK' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsStack('ABFCJACDBK')).toBe(2)
})

test(`'ABFCACDB' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsStackJs('ABFCACDB')).toBe(2)
})

test(`'ACBBD' toBe 5`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsStackJs('ACBBD')).toBe(5)
})

test(`'ABFCJACDBK' toBe 2`, () => {
  expect(minimumStringLengthAfterRemovingSubstringsStackJs('ABFCJACDBK')).toBe(2)
})

2696. 删除子串后的字符串最小长度 ​

示例 ​

示例 1 ​

示例 2 ​

代码 ​

测试代码 ​

2696. 删除子串后的字符串最小长度

示例

示例 1

示例 2

代码

测试代码