2182. 构造限制重复的字符串

2182. 构造限制重复的字符串

给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。

示例

示例 1

输入：s = "cczazcc", repeatLimit = 3

输出："zzcccac"

解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。

字母 'a' 连续出现至多 1 次。

字母 'c' 连续出现至多 3 次。

字母 'z' 连续出现至多 2 次。

因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。

该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。

注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。

示例 2

输入：s = "aababab", repeatLimit = 2

输出："bbabaa"

解释：

使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。

字母 'a' 连续出现至多 2 次。

字母 'b' 连续出现至多 2 次。

因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。

该字符串是字典序最大的 repeatLimitedString ，所以返回 "bbabaa" 。

注意，尽管 "bbabaaa" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。

提示

1. 1 <= repeatLimit <= s.length <= 105
2. s 由小写英文字母组成

代码

javascript

// 2182. 构造限制重复的字符串
// https://leetcode.cn/problems/construct-string-with-repeat-limit/description/

export function repeatLimitedString (s, repeatLimit) {
  const N = 26
  let count = new Array(N).fill(0)
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++
  }
  let res = ''
  let limit = 0
  let index = N - 1
  let JIndex = N - 2
  while (index >= 0 && JIndex >= 0) {
    if (count[index] === 0) {
      index--
      limit = 0
    } else if (limit < repeatLimit) {
      count[index]--
      limit++
      res += String.fromCharCode(index + 97)
    } else if (JIndex >= index || count[JIndex] === 0) {
      JIndex--
    } else {
      count[JIndex]--
      limit = 0
      res += String.fromCharCode(JIndex + 97)
    }
  }
  return res
};

typescript

// 2182. 构造限制重复的字符串
// https://leetcode.cn/problems/construct-string-with-repeat-limit/description/

export function repeatLimitedString (s: string, repeatLimit: number): string {
  const N = 26
  let count = new Array(N).fill(0)
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++
  }
  let res = ''
  let limit = 0
  let index = N - 1
  let JIndex = N - 2
  while (index >= 0 && JIndex >= 0) {
    if (count[index] === 0) {
      index--
      limit = 0
    } else if (limit < repeatLimit) {
      count[index]--
      limit++
      res += String.fromCharCode(index + 97)
    } else if (JIndex >= index || count[JIndex] === 0) {
      JIndex--
    } else {
      count[JIndex]--
      limit = 0
      res += String.fromCharCode(JIndex + 97)
    }
  }
  return res
};

测试代码

test

import { expect, test } from 'vitest'
import { repeatLimitedString } from './typescript.ts'
import { repeatLimitedString as repeatLimitedStringJs } from './javascript.js'

test(`repeatLimitedString('cczazcc', 3) toBe 'zzcccac'`, () => {
  expect(repeatLimitedString('cczazcc', 3)).toBe('zzcccac')
})

test(`repeatLimitedString('aababab', 2) toBe 'bbabaa'`, () => {
  expect(repeatLimitedString('aababab', 2)).toBe('bbabaa')
})


test(`repeatLimitedStringJs('cczazcc', 3) toBe 'zzcccac'`, () => {
  expect(repeatLimitedStringJs('cczazcc', 3)).toBe('zzcccac')
})

test(`repeatLimitedStringJs('aababab', 2) toBe 'bbabaa'`, () => {
  expect(repeatLimitedStringJs('aababab', 2)).toBe('bbabaa')
})