Watch 10 video solutions for Calculate Digit Sum of a String, a easy level problem involving String, Simulation. This walkthrough by Coding Decoded has 2,368 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |