InterviewDB
Question
Limit Consecutive Duplicates: Remove Excess Repeated Characters
phone
Question Details
Problem
Given a string s and an integer limit, remove the minimum number of characters so that no character appears more than limit times consecutively.
Return the resulting string.
python
def limit_consecutive_duplicates(s: str, limit: int) -> str:
pass
**Input**: s = "aaabbbcc", limit = 2
Output: "aabbcc"
# 'a' appears 3x consecutively -> remove 1 -> 'aa'
# 'b' appears 3x -> remove 1 -> 'bb'
**Input**: s = "aaa", limit = 1
Output: "a"
**Input**: s = "aabbcc", limit = 3
Output: "aabbcc" # already valid
**Input**: s = "", limit = 2
Output: ""
Follow-ups
- Is your solution a single pass? Prove it produces the minimum number of removals.
- What is the time and space complexity?
- Extend to limit the total (not just consecutive) occurrences of any character to
limit. - If you cannot remove characters but can rearrange them, how would you solve the problem?
Full Details
Problem
Given a string s and an integer limit, remove the minimum number of characters so that no character appears more than limit times consecutively.
Return the resulting string.
python
def limit_consecutive_duplicates(s: str, limit: int) -> str:
pass
**Input**: s = "aaabbbcc", limit = 2
Output: "aabbcc"
# 'a' appears 3x consecutively -> remove 1 -> 'aa'
# 'b' appears 3x -> remove 1 -> 'bb'
**Input**: s = "aaa", limit = 1
Output: "a"
**Input**: s = "aabbcc", limit = 3
Output: "aabbcc" # already valid
**Input**: s = "", limit = 2
Output: ""
Follow-ups
- Is your solution a single pass? Prove it produces the minimum number of removals.
- What is the time and space complexity?
- Extend to limit the total (not just consecutive) occurrences of any character to
limit. - If you cannot remove characters but can rearrange them, how would you solve the problem?
Free preview. Unlock all Spotify questions →