# Calculate Digit Sum of a String
**Difficulty:** EASY
[External](https://leetcode.com/problems/calculate-digit-sum-of-a-string)
Canonical: https://scaleengineer.com/dsa/problems/calculate-digit-sum-of-a-string
**Data structures:** String
---
## Problem
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:

1. **Divide** `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`.
2. **Replace** each group of `s` with a string representing the sum of all its digits. For example, `"346"` is replaced with `"13"` because `3 + 4 + 6 = 13`.
3. **Merge** consecutive groups together to form a new string. If the length of the string is greater than `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 <= 100`
* `2 <= k <= 100`
* `s` consists of digits only.

# Approaches
## Iterative Simulation with String Concatenation
This approach directly simulates the process described in the problem. It repeatedly calculates the digit sums of groups and rebuilds the string in a loop. For string construction, it uses the `+` operator for concatenation, which is known to be inefficient in Java when used in a loop.
**Time:** O(R * (N/k)²), where `N` is the maximum length of the string `s`, `R` is the number of rounds, and `k` is the group size. The inefficiency comes from string concatenation in a loop. If there are `M = ceil(N/k)` groups, building the new string takes time proportional to the sum of lengths of all intermediate strings, which is O(M²). This makes each round's complexity quadratic in the number of groups. · **Space:** O(N), where `N` is the maximum length of `s`. This space is required to store the new string `next_s` and the various intermediate strings created during concatenation in each round.
**Pros:** Conceptually simple and a direct translation of the problem statement.
**Cons:** Very inefficient for string building. The use of `+` for string concatenation inside a loop leads to quadratic time complexity relative to the number of groups, which can be slow if the string is long and `k` is small.
### Explanation
The core idea is to loop as long as the string's length exceeds `k`. In each iteration, a new string is built to store the result of the current round.\n\n*   A `while` loop checks the condition `s.length() > k`.\n*   Inside the loop, a new empty string, `next_s`, is created.\n*   The code iterates through the current string `s` by `k` characters at a time.\n*   For each group of characters, it calculates the sum of their integer values.\n*   This sum is converted to a string and appended to `next_s` using `next_s += sumString;`. This operation is inefficient because strings are immutable in Java. Each concatenation creates a new `StringBuilder`, performs the append, and then creates a new `String` object, leading to poor performance, especially with many groups.\n*   After processing all groups, `s` is updated to `next_s`, and the loop continues for the next round.
### Algorithm
*   Start a `while` loop that continues as long as `s.length() > k`.\n*   Initialize an empty string `temp` to store the result of the current round.\n*   Iterate through the current string `s` with an index `i`, starting at 0 and incrementing by `k` in each step.\n*   For each `i`, extract the group as a substring from `i` to `min(i + k, s.length())`.\n*   Calculate the sum of the digits within this group.\n*   Convert the sum to its string representation.\n*   Append this sum-string to `temp` using the `+` operator.\n*   After the loop over all groups finishes, update `s` with the value of `temp`.\n*   When the `while` loop terminates, return the final string `s`.

## Optimized Iterative Simulation with StringBuilder
This is the standard and efficient approach for this problem. It follows the same iterative simulation logic but replaces the inefficient string concatenation with a mutable `StringBuilder`. This significantly improves the performance of building the new string in each round.
**Time:** O(R * N), where `N` is the maximum length of the string `s` and `R` is the number of rounds. Each round takes O(nᵢ) time, where nᵢ is the length of the string in that round. This involves one pass to calculate sums and one effective pass to build the new string using `StringBuilder`. The total time is the sum of lengths across all rounds. Since the length tends to decrease, the total time is dominated by the initial rounds, making it very efficient. · **Space:** O(N), where `N` is the maximum length of `s`. The space is primarily used for the `StringBuilder`, which can grow up to a size proportional to `N`.
**Pros:** Highly efficient due to the use of `StringBuilder` for string construction.; This is the optimal and standard solution for this type of simulation problem.
**Cons:** Slightly more verbose than the naive approach, requiring familiarity with the `StringBuilder` class.
### Explanation
This approach refines the first one by using a `StringBuilder` for efficient string construction, which is the idiomatic way to handle such tasks in Java.\n\n*   The overall structure is a `while` loop that runs as long as `s.length() > k`.\n*   Inside the loop, a `StringBuilder` is initialized.\n*   The code iterates through the current string `s` in groups of size `k`. Instead of creating substrings, it can iterate using indices for better performance.\n*   For each group, the digit sum is calculated.\n*   The `append()` method of the `StringBuilder` is used to add the string representation of the sum. This operation is much faster than `+` concatenation as it modifies an internal buffer in amortized constant time.\n*   Once all groups are processed, the `StringBuilder` is converted to a final string using `toString()`, and `s` is updated.\n*   This process repeats until the length of `s` is no longer greater than `k`.
### Algorithm
*   Start a `while` loop that continues as long as `s.length() > k`.\n*   Initialize a new `StringBuilder sb`.\n*   Iterate through the current string `s` with an index `i`, starting at 0 and incrementing by `k`.\n*   For each group starting at `i`:\n    *   Initialize a `sum` variable to 0.\n    *   Loop from index `j = i` to `min(i + k, s.length()) - 1`.\n    *   In the inner loop, add the numeric value of the character `s.charAt(j)` to `sum`.\n    *   After calculating the sum for the group, append it to the `StringBuilder` using `sb.append(sum)`.\n*   After the outer loop finishes, update `s` to `sb.toString()`.\n*   When the `while` loop terminates, return `s`.

# Solutions
### Java

```java
class Solution {
public
  String digitSum(String s, int k) {
    while (s.length() > k) {
      int n = s.length();
      StringBuilder t = new StringBuilder();
      for (int i = 0; i < n; i += k) {
        int x = 0;
        for (int j = i; j < Math.min(i + k, n); ++j) {
          x += s.charAt(j) - '0';
        }
        t.append(x);
      }
      s = t.toString();
    }
    return s;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @param {number} k * @return {string} */ var digitSum =
  function (s, k) {
    while (s.length > k) {
      const t = [];
      for (let i = 0; i < s.length; i += k) {
        const x = s
          .slice(i, i + k)
          .split("")
          .reduce((a, b) => a + +b, 0);
        t.push(x);
      }
      s = t.join("");
    }
    return s;
  };

```

### CPP

```cpp
class Solution {
public:
  string digitSum(string s, int k) {
    while (s.size() > k) {
      string t;
      int n = s.size();
      for (int i = 0; i < n; i += k) {
        int x = 0;
        for (int j = i; j < min(i + k, n); ++j) {
          x += s[j] - '0';
        }
        t += to_string(x);
      }
      s = t;
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def digitSum(self, s: str, k: int) -> str: while len(s) > k: t = [] n = len(s) for i in range(0, n, k): x = 0 for j in range(i, min(i + k, n)): x += int(s[j]) t . append(str(x)) s = "" . join(t) return s

```