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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6

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.

Solution

Method 1 – Simulation by Grouping and Summing

Intuition

We repeatedly split the string into groups of size k, sum the digits in each group, and concatenate the results. This process is repeated until the string’s length is less than or equal to k. This direct simulation matches the problem’s requirements and is efficient for the given constraints.

Approach

  1. While the length of s is greater than k:
    • Split s into consecutive groups of size k.
    • For each group, sum its digits and convert the sum to a string.
    • Concatenate all group sums to form the new s.
  2. Return s when its length is less than or equal to k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    string digitSum(string s, int k) {
        while (s.length() > k) {
            string ns = "";
            for (int i = 0; i < s.length(); i += k) {
                int sum = 0;
                for (int j = i; j < min(i + k, (int)s.length()); ++j) {
                    sum += s[j] - '0';
                }
                ns += to_string(sum);
            }
            s = ns;
        }
        return s;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func digitSum(s string, k int) string {
    for len(s) > k {
        ns := ""
        for i := 0; i < len(s); i += k {
            sum := 0
            for j := i; j < i+k && j < len(s); j++ {
                sum += int(s[j] - '0')
            }
            ns += strconv.Itoa(sum)
        }
        s = ns
    }
    return s
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

class Solution {
    fun digitSum(s: String, k: Int): String {
        var str = s
        while (str.length > k) {
            var ns = StringBuilder()
            var i = 0
            while (i < str.length) {
                var sum = 0
                for (j in i until minOf(i + k, str.length)) {
                    sum += str[j].digitToInt()
                }
                ns.append(sum)
                i += k
            }
            str = ns.toString()
        }
        return str
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def digitSum(self, s: str, k: int) -> str:
        while len(s) > k:
            ns = ''
            for i in range(0, len(s), k):
                ns += str(sum(int(x) for x in s[i:i+k]))
            s = ns
        return s
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn digit_sum(s: String, k: i32) -> String {
        let mut s = s;
        let k = k as usize;
        while s.len() > k {
            let mut ns = String::new();
            let bytes = s.as_bytes();
            let mut i = 0;
            while i < s.len() {
                let mut sum = 0;
                for j in i..std::cmp::min(i + k, s.len()) {
                    sum += (bytes[j] - b'0') as u32;
                }
                ns += &sum.to_string();
                i += k;
            }
            s = ns;
        }
        s
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    digitSum(s: string, k: number): string {
        while (s.length > k) {
            let ns = '';
            for (let i = 0; i < s.length; i += k) {
                let sum = 0;
                for (let j = i; j < Math.min(i + k, s.length); ++j) {
                    sum += Number(s[j]);
                }
                ns += sum.toString();
            }
            s = ns;
        }
        return s;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — Each round processes all digits, and the number of rounds is at most O(n).
  • 🧺 Space complexity: O(n) — For the new string in each round.