Scale Engineer

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:

  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

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.

Solutions

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;  }}

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 →

Next problem