2243. Calculate Digit Sum of a String

LeetCode 力扣

1. Description

Given a digit string s and an integer k, repeatedly transform s while its length exceeds k.
In each round, split s from left to right into groups of k characters; the final group may be shorter. For each group, add its digits and write the sum in decimal. Concatenate these sums in order to obtain the string for the next round.
Return the final string once its length is at most k.

2. Example

Example 1

Input: s = “11111222223”, k = 3
Output: “135”
Explanation: The first round groups the digits as “111”, “112”, “222”, and “23”, producing “3465”. The next round groups “346” and “5”, producing “135”. Its length is 3, so the process stops.

Example 2

Input: s = “00000000”, k = 3
Output: “000”
Explanation: The groups “000”, “000”, and “00” each contribute “0”, yielding “000”. Its length equals k.

3. Constraints

  • 1 <= s.length <= 100
  • 2 <= k <= 100
  • s consists of digits only.

4. Solutions

Simulation

n = str.size()
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string digitSum(string str, int k) {

        while (str.size() > k) {
            string result;
            for (int left = 0, n = str.size(); left < n; left += k) {
                int sum = 0;
                for (int i = left, right = min(n, left + k); i < right; ++i) {
                    sum += str[i] - '0';
                }

                result += to_string(sum);
            }

            str = move(result);
        }

        return str;
    }
};
comments powered by Disqus