Calculate Digit Sum of a String

Difficulty: Easy | Acceptance: 67.80% | Paid: No Topics: String, Simulation

You are given a string s consisting of digits and an integer k.

We want to perform the following operation on s until the length of s is less than or equal to k:

1. Divide s into consecutive groups of size k. The first group may have fewer than k characters.
2. Replace each group with the sum of the digits in the group.
3. Concatenate the groups to form a new string.

Return the resulting string.

• Examples
• Constraints
• Approach 1: Iterative Simulation
• Approach 2: Recursive Simulation

Examples

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 <= 100
s consists of digits only.
1 <= k <= 10

Approach 1: Iterative Simulation

Intuition We can directly simulate the process described in the problem. We repeatedly iterate through the string, chunking it into groups of size k, summing the digits in each group, and building a new string until the length constraint is met.

Steps

• While the length of s is greater than k:
  • Initialize an empty string next_s to store the result of the current pass.
  • Iterate through s with a step size of k.
  • For each chunk, calculate the sum of its digits.
  • Append the string representation of this sum to next_s.
  • Update s to be next_s.
• Return s.

class Solution:
    def digitSum(self, s: str, k: int) -> str:
        while len(s) > k:
            next_s = []
            for i in range(0, len(s), k):
                group = s[i:i+k]
                total = sum(int(c) for c in group)
                next_s.append(str(total))
            s = "".join(next_s)
        return s

Complexity

• Time: O(N²) in the worst case (where N is the length of the string). If k=1, the string length reduces by 1 each time, and we process the whole string each time. However, given N <= 100, this is effectively O(1) for practical purposes.
• Space: O(N) to store the new string in each iteration.
• Notes: This is the most straightforward approach and perfectly efficient given the constraints.

Approach 2: Recursive Simulation

Intuition The process of reducing the string is naturally recursive. If the string length is already <= k, we are done. Otherwise, we perform one round of grouping and summing, then recursively solve the problem for the new string.

Steps

• Base Case: If the length of s is less than or equal to k, return s.
• Recursive Step:
  • Perform one iteration of the grouping and summing logic (same as the inner loop of the iterative approach) to generate next_s.
  • Return the result of digitSum(next_s, k).

class Solution:
    def digitSum(self, s: str, k: int) -> str:
        if len(s) <= k:
            return s
        
        next_s = []
        for i in range(0, len(s), k):
            group = s[i:i+k]
            total = sum(int(c) for c in group)
            next_s.append(str(total))
        
        return self.digitSum("".join(next_s), k)

Complexity

• Time: O(N²) same as the iterative approach.
• Space: O(N) for the recursion stack and the new string. The depth of recursion is proportional to the number of iterations.
• Notes: This approach is elegant but uses stack space which could be a concern for very large inputs (though not an issue here).