2182. Construct String With Repeat Limit
Approach
Greedy from largest char; append up to repeatLimit, then insert next largest as separator.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
A heap (priority queue) gives O(log n) insert and O(1) peek with O(log n) removal. In C#, use PriorityQueue<TElement, TPriority> (.NET 6+). Classic patterns: top-K elements (min-heap of size K), merge K sorted lists, Dijkstra's shortest path, and median in a stream (two heaps).
// Approach: Greedy from largest char; append up to repeatLimit, then insert next largest as separator.
// Time: O(n) Space: O(n)
public class Solution
{
public string RepeatLimitedString(string s, int repeatLimit)
{
StringBuilder sb = new StringBuilder();
int[] count = new int[26];
foreach (char c in s)
count[c - 'a']++;
while (true)
{
bool addOne = sb.Length > 0 && ShouldAddOne(sb, count);
int i = GetLargestChar(sb, count);
if (i == -1)
break;
int repeats = addOne ? 1 : Math.Min(count[i], repeatLimit);
sb.Append(new string((char)('a' + i), repeats));
count[i] -= repeats;
}
return sb.ToString();
}
private bool ShouldAddOne(StringBuilder sb, int[] count)
{
for (int i = 25; i >= 0; --i)
{
if (count[i] > 0)
return sb[sb.Length - 1] == (char)('a' + i);
}
return false;
}
private int GetLargestChar(StringBuilder sb, int[] count)
{
for (int i = 25; i >= 0; --i)
{
if (count[i] > 0 && (sb.Length == 0 || sb[sb.Length - 1] != (char)('a' + i)))
return i;
}
return -1;
}
}