Turing.com Online Assessment Algorithm Question Experience

Problem Statement Given a string num consisting of digits and an integer k, reorder the digits to form the lexicographically largest valid string. A string is considered valid if no specific d

Problem Statement Given a string num consisting of digits and an integer k, reorder the digits to form the lexicographically largest valid string. A string is considered valid if no specific digit appears consecutively more than k times. The goal is to maximize the value of the resulting number using the available digit frequencies. Constraints * $1 \le k \le \text{num.length} \le 10^7$ * num consists exclusively of digits 0 through 9. Approach The problem requires a greedy strategy to ensure the number is as large as possible. 1. Frequency Count: Calculate the frequency of every digit (0-9) present in the input string. 2. Greedy Construction: Iterate through the digits from largest (9) to smallest (0). * Append the current largest available digit to the result string up to k times, or until its count reaches zero. * If the limit k is reached but instances of the current digit still remain, a "separator" digit is required to break the sequence. * Identify the next largest available digit to serve as this separator. Append it once to the result and decrement its count. * Return to the primary largest digit and continue appending. 3. Termination: If the current largest digit has reached the consecutive limit k and no smaller digits are available to act as separators, the construction ends. Examples * Input: num = "3391933", k = 3 * Output: "9933313" * Logic: The largest digits (9s) are placed first. The 3s are placed next, but limited to a streak of three. The 1 is used as a separator, allowing the final 3 to be placed. * Input: num = "1121212", k = 2 * Output: "221211" * Logic: The 2s are prioritized. After two 2s, a 1 is used as a separator. This pattern continues until no separators remain to accommodate the final 1.