A naukri.com initiative
Dev
1w
167
Image Credit: Dev
2182. Construct String With Repeat Limit
- 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.
- Return the lexicographically largest repeatLimitedString possible.
- We use a greedy approach to prioritize lexicographically larger characters while ensuring that no character exceeds the repeatLimit consecutively.
- The approach uses a priority queue (max heap) to process characters in lexicographically descending order and ensures that no character appears more than the repeatLimit times consecutively.
- We use all of the characters from s to construct the repeatLimitedString.
- The time complexity of the solution is O(n + 26 log 26) ≈ O(n)and the space complexity is O(26) for the frequency array and O(26) for the heap.
- This implementation works efficiently within the constraints.
- Test cases: echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: "zzcccac" and echo repeatLimitedString("aababab", 2) . "\n"; // Output: "bbabaa".
- Edge cases: When s contains only one unique character, when repeatLimit is equal to 1 or When all characters in s are unique.
- Follow author on LinkedIn and GitHub for more helpful content.
Read Full Article
10 Likes
For uninterrupted reading, download the app