You are given a string s consisting of digits and an integer k.
A round can be completed if the length of s is greater than k. In one round, do the following:
s into consecutive groups of size k such that the first k characters are in the first group, the next k characters are in the second group, and so on. Note that the size of the last group can be smaller than k.s with a string representing the sum of all its digits. For example, "346" is replaced with "13" because 3 + 4 + 6 = 13.k, repeat from step 1.Return s after all rounds have been completed.
Example 1:
Input: s = "11111222223", k = 3 Output: "135" Explanation: - For the first round, we divide s into groups of size 3: "111", "112", "222", and "23". Then we calculate the digit sum of each group: 1 + 1 + 1 = 3, 1 + 1 + 2 = 4, 2 + 2 + 2 = 6, and 2 + 3 = 5. So, s becomes "3" + "4" + "6" + "5" = "3465" after the first round. - For the second round, we divide s into "346" and "5". Then we calculate the digit sum of each group: 3 + 4 + 6 = 13, 5 = 5. So, s becomes "13" + "5" = "135" after second round. Now, s.length <= k, so we return "135" as the answer.
Example 2:
Input: s = "00000000", k = 3 Output: "000" Explanation: We divide s into "000", "000", and "00". Then we calculate the digit sum of each group: 0 + 0 + 0 = 0, 0 + 0 + 0 = 0, and 0 + 0 = 0. s becomes "0" + "0" + "0" = "000", whose length is equal to k, so we return "000".
Constraints:
1 <= s.length <= 1002 <= k <= 100s consists of digits only.Problem Overview: You are given a numeric string s and an integer k. Repeatedly split the string into groups of size k, compute the digit sum of each group, and concatenate those sums to form a new string. Continue the process until the string length becomes less than or equal to k.
Approach 1: Iterative Simulation (O(n) time, O(n) space)
This approach directly simulates the process described in the problem. While the string length is greater than k, iterate through the string in chunks of size k. For each chunk, convert characters to digits, compute the sum, and append the result to a new string builder. After processing all groups, replace the original string with the newly constructed string and repeat the process. Each digit participates in a small constant number of summations across iterations, keeping the total time complexity O(n) and space O(n). This is the most practical solution and relies on simple string manipulation and simulation.
Approach 2: Recursive Simulation (O(n) time, O(n) space)
The same grouping logic can be expressed recursively. Define a function that takes the current string. If its length is less than or equal to k, return it as the base case. Otherwise, iterate through the string in steps of k, compute the digit sum for each segment, and build the next string. Then recursively call the function with this newly generated string. Each recursive call reduces the string length, so the recursion depth remains small. Time complexity stays O(n) since each digit is processed a limited number of times, while auxiliary space is O(n) due to the new strings created and recursion stack. This version highlights the repeated transformation pattern and demonstrates a clean use of recursion.
Recommended for interviews: The iterative simulation approach is what interviewers typically expect. It directly follows the problem statement, avoids recursion overhead, and clearly demonstrates control over string iteration and chunk processing. Implementing the recursive variant can show deeper understanding of problem structure, but the iterative solution is simpler, easier to reason about, and usually preferred in production code.
The iterative approach involves reducing the problem step by step. We use a loop to partition the string into groups, sum the digits in each group, and form a new string. This process is repeated until the length of the new string is less than or equal to k.
The C code uses dynamic memory allocation to handle repeated transformation of the string. During each iteration, the string is partitioned, digit sums are calculated for each group, and a new string is constructed from these sums. This continues until the resulting string's length is not greater than k.
The time complexity is O(n * m), where n is the length of the string and m is log base 10 of the sum of digits. The space complexity is O(n).
The recursive approach uses a function to perform the digit summation operation once and calls itself as long as the resulting string has a length greater than k. This method translates the iterative mechanism into a recursion pattern.
In C, recursion is used to call the digitSumStringRecursive function repeatedly if the result's length is greater than k. This effectively captures the same repeated operation pattern as iterative methods, but through recursive calls.
The time complexity is O(n * m), while the call stack space usage also leads to O(n) space complexity overall.
| Approach | Complexity |
|---|---|
| Iterative Approach | The time complexity is O(n * m), where n is the length of the string and m is log base 10 of the sum of digits. The space complexity is O(n). |
| Recursive Approach | The time complexity is O(n * m), while the call stack space usage also leads to O(n) space complexity overall. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(n) | O(n) | Best general solution. Simple loop-based implementation and preferred for interviews. |
| Recursive Simulation | O(n) | O(n) | Useful when expressing repeated transformations recursively or practicing recursion patterns. |
Calculate Digit Sum of a String | Leetcode 2243 | Strings | Contest 289 🔥🔥 • Coding Decoded • 2,368 views views
Watch 9 more video solutions →Practice Calculate Digit Sum of a String with our built-in code editor and test cases.
Practice on FleetCode