Calculate Digit Sum of a String

Easy

#2043Time: 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.

Data structures

String

Prompt

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:

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.
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.
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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

Complexity

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`.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  String digitSum(String s, int k) {4    while (s.length() > k) {5      int n = s.length();6      StringBuilder t = new StringBuilder();7      for (int i = 0; i < n; i += k) {8        int x = 0;9        for (int j = i; j < Math.min(i + k, n); ++j) {10          x += s.charAt(j) - '0';11        }12        t.append(x);13      }14      s = t.toString();15    }16    return s;17  }18}

1/** * @param {string} s * @param {number} k * @return {string} */ var digitSum =2  function (s, k) {3    while (s.length > k) {4      const t = [];5      for (let i = 0; i < s.length; i += k) {6        const x = s7          .slice(i, i + k)8          .split("")9          .reduce((a, b) => a + +b, 0);10        t.push(x);11      }12      s = t.join("");13    }14    return s;15  };

1class Solution {2public:3  string digitSum(string s, int k) {4    while (s.size() > k) {5      string t;6      int n = s.size();7      for (int i = 0; i < n; i += k) {8        int x = 0;9        for (int j = i; j < min(i + k, n); ++j) {10          x += s[j] - '0';11        }12        t += to_string(x);13      }14      s = t;15    }16    return s;17  }18};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem