2182. Construct String With Repeat Limit #

Problem #

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

• 1 <= repeatLimit <= s.length <= 10^5
• s consists of lowercase English letters.

Problem Summary #

Given a string s and an integer repeatLimit, use the characters in s to construct a new string repeatLimitedString such that no letter appears consecutively more than repeatLimit times. You do not have to use all the characters in s.

Return the lexicographically largest repeatLimitedString.

If at the first position where strings a and b differ, the letter in string a appears later in the alphabet than the corresponding letter in string b, then string a is considered lexicographically larger than string b. If the first min(a.length, b.length) characters of the strings are the same, then the longer string is lexicographically larger.

Solution Approach #

• Use a greedy approach. Since the problem asks for the lexicographically largest string, first choose from the lexicographically largest letter. Then choose the minimum of the count of the current lexicographically largest letter and limit. If there are many occurrences of the current lexicographically largest letter, more than limit, we cannot keep choosing it. After choosing limit occurrences, we need to choose the next lexicographically largest letter, and after choosing this letter, choose the lexicographically largest letter again. This is because limit restricts a letter from appearing consecutively more than limit times. Repeat this process until all letters have been chosen. The string arranged by this strategy has the maximum lexicographical order.

Code #

package leetcode

func repeatLimitedString(s string, repeatLimit int) string {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[int(c-'a')]++
	}
	var ns []byte
	for i := 25; i >= 0; {
		k := i - 1
		for cnt[i] > 0 {
			for j := 0; j < min(cnt[i], repeatLimit); j++ {
				ns = append(ns, byte(i)+'a')
			}
			cnt[i] -= repeatLimit
			if cnt[i] > 0 {
				for ; k >= 0 && cnt[k] == 0; k-- {
				}
				if k < 0 {
					break
				} else {
					ns = append(ns, byte(k)+'a')
					cnt[k]--
				}
			}
		}
		i = k
	}
	return string(ns)
}
func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}