LeetCode 2243 - Calculate Digit Sum of a String

LeetCode Problem 2243

Difficulty: 🟢 Easy
Topics: String, Simulation

Solution

Problem Understanding

This problem asks us to repeatedly transform a numeric string until its length becomes less than or equal to a given integer k.

We are given two inputs:

• s, a string consisting only of digit characters ('0' through '9')
• k, an integer that determines the size of groups used during each transformation round

The process works in repeated rounds. In each round, we divide the string into consecutive chunks of size k. Most groups will have exactly k characters, but the final group may be smaller if the string length is not divisible by k.

For every group, we calculate the sum of its digits and replace that group with the decimal string representation of the sum. After processing all groups, we concatenate all resulting sums into a new string. If this newly formed string still has a length greater than k, we repeat the process.

The goal is to return the final string once its length becomes less than or equal to k.

For example, if s = "346" and k = 3, the entire string forms one group. The digit sum is:

3 + 4 + 6 = 13

So "346" becomes "13".

An important detail is that digit sums may produce multi digit numbers. For instance, summing digits can result in "13" or "27", not just a single digit. This means the resulting string length may shrink slowly, which is why repeated rounds are necessary.

The constraints are very small:

• 1 <= s.length <= 100
• 2 <= k <= 100

Since the string length is at most 100, efficiency is not a major concern. Even a straightforward simulation is fast enough. However, we still want a clean and optimal implementation.

Several edge cases are important:

• If s.length <= k initially, no rounds are needed, and we return s immediately.
• The last group may contain fewer than k digits, so we must handle incomplete groups correctly.
• Digit sums can create multi digit values, which affects the next round's grouping.
• Strings containing many zeros, such as "00000000", should preserve leading zeros in the resulting string because each group sum is converted independently before concatenation.

Approaches

Brute Force Approach

The brute force solution directly simulates the problem statement.

In each round, we iterate through the string in chunks of size k. For every chunk, we compute the sum of its digits by iterating through each character and converting it to an integer. We then convert the sum back into a string and append it to a temporary result.

Once all groups are processed, we replace s with the newly constructed string and repeat until s.length <= k.

This approach is correct because it exactly follows the rules described in the problem statement. Every transformation round is performed as required.

Although this is called a brute force approach, it is already efficient enough because the maximum input size is very small. The repeated reconstruction of strings and repeated digit summation remain inexpensive.

Optimal Approach

The key observation is that the problem is fundamentally a simulation problem. There is no shortcut formula or advanced data structure needed because each transformation depends on the result of the previous round.

The optimal solution is therefore to simulate the process carefully and efficiently. Instead of repeatedly creating many intermediate strings inefficiently, we use a list (or string builder equivalent) to construct the next string in linear time during each round.

At every round:

1. Process the string in chunks of size k.
2. Compute each chunk's digit sum.
3. Append the sum as a string.
4. Merge all pieces into the next version of s.

Since the string shrinks over time, the total work remains small.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Directly simulates every round with repeated string rebuilding
Optimal	O(n²)	O(n)	Efficient simulation using linear string construction

Here, n represents the maximum length of the string. Since n <= 100, this is easily fast enough.

Algorithm Walkthrough

Optimal Algorithm

1. Start a loop that continues while the length of s is greater than k.

We only perform transformation rounds when required. If s.length <= k, the process stops immediately. 2. Create an empty list (or string builder) to construct the next version of the string.

Building strings incrementally is more efficient than repeated concatenation. 3. Iterate through s in steps of size k.

For each position i, take the substring from i to i + k. The last group may naturally be smaller. 4. Compute the digit sum of the current group.

Iterate through every character in the group and add its numeric value by subtracting '0' or converting to an integer. 5. Convert the computed sum into a string and append it to the result builder.

This preserves multi digit sums correctly. 6. After processing all groups, merge the pieces into a new string.

Replace s with this newly generated value. 7. Repeat until len(s) <= k. 8. Return the final string.

Why it works

The algorithm works because it preserves the exact transformation rules of the problem at every round. Each iteration correctly partitions the string into consecutive groups of size k, computes the sum of digits for every group, converts those sums into strings, and concatenates them in order.

The invariant is that after each loop iteration, s is exactly the transformed version required by one valid round of the problem. Since the string eventually becomes short enough, the process terminates with the correct answer.

Python Solution

class Solution:
    def digitSum(self, s: str, k: int) -> str:
        while len(s) > k:
            next_parts = []

            for i in range(0, len(s), k):
                group = s[i:i + k]

                digit_sum = 0
                for digit in group:
                    digit_sum += int(digit)

                next_parts.append(str(digit_sum))

            s = "".join(next_parts)

        return s

The implementation follows the algorithm exactly.

The while loop ensures we keep processing rounds as long as the string length exceeds k. During each round, next_parts stores the transformed result for every group.

The for loop processes the string in chunks of size k using Python slicing. The expression s[i:i+k] automatically handles the last partial group safely.

For every group, we compute digit_sum by iterating through each character and converting it to an integer using int(digit).

After calculating the sum, we convert it back to a string and append it to next_parts. Once all groups are processed, "".join(next_parts) efficiently constructs the new string.

Eventually, the loop stops when len(s) <= k, and the final string is returned.

Go Solution

import (
	"strconv"
	"strings"
)

func digitSum(s string, k int) string {
	for len(s) > k {
		var builder strings.Builder

		for i := 0; i < len(s); i += k {
			end := i + k
			if end > len(s) {
				end = len(s)
			}

			sum := 0
			for j := i; j < end; j++ {
				sum += int(s[j] - '0')
			}

			builder.WriteString(strconv.Itoa(sum))
		}

		s = builder.String()
	}

	return s
}

The Go implementation follows the same logic as the Python version but uses strings.Builder for efficient string construction.

Since Go does not support Python style slicing behavior automatically for out of bounds endpoints, we manually compute end and cap it at len(s) to handle the last smaller group safely.

Digit conversion is done with:

int(s[j] - '0')

This converts the byte character into its numeric value efficiently.

strconv.Itoa() converts the computed sum back into a string before appending it to the builder.

There are no concerns about integer overflow because the maximum digit sum is very small. Even summing 100 digits of 9 produces only 900.

Worked Examples

Example 1

Input:

s = "11111222223"
k = 3

Round 1

Group	Digit Sum	Result
"111"	3	"3"
"112"	4	"4"
"222"	6	"6"
"23"	5	"5"

New string:

s = "3465"

Round 2

Group	Digit Sum	Result
"346"	13	"13"
"5"	5	"5"

New string:

s = "135"

Now:

len("135") = 3

Since 3 <= k, stop.

Final answer:

"135"

Example 2

Input:

s = "00000000"
k = 3

Round 1

Group	Digit Sum	Result
"000"	0	"0"
"000"	0	"0"
"00"	0	"0"

New string:

s = "000"

Now:

len("000") = 3

Since 3 <= k, stop.

Final answer:

"000"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Multiple rounds process the string, each round scans the current string
Space	O(n)	Temporary storage is needed for the rebuilt string

The string can be processed several times, and each round scans all characters currently present. In the worst case, the string shrinks slowly across rounds, leading to quadratic time complexity.

However, because n <= 100, the actual runtime is extremely small in practice.

Test Cases

solution = Solution()

assert solution.digitSum("11111222223", 3) == "135"  # Example 1
assert solution.digitSum("00000000", 3) == "000"  # Example 2

assert solution.digitSum("123", 3) == "123"  # Length already equal to k
assert solution.digitSum("5", 2) == "5"  # Single digit input
assert solution.digitSum("999999", 2) == "99"  # Multiple rounds with multi digit sums
assert solution.digitSum("123456789", 2) == "99"  # Uneven transformations
assert solution.digitSum("10", 2) == "10"  # No processing needed
assert solution.digitSum("987654321", 4) == "108"  # Last group smaller than k
assert solution.digitSum("999", 2) == "27"  # Multi digit group sum
assert solution.digitSum("0000", 2) == "00"  # Preserves zeros

Test	Why
"11111222223", 3	Validates Example 1
"00000000", 3	Validates Example 2
"123", 3	Confirms no transformation when length equals k
"5", 2	Tests minimum length input
"999999", 2	Verifies repeated rounds and large digit sums
"123456789", 2	Tests multiple transformations
"10", 2	Ensures unchanged result when already valid
"987654321", 4	Validates handling of incomplete final group
"999", 2	Ensures multi digit sums are preserved
"0000", 2	Confirms zeros remain correctly represented

Edge Cases

String Length Already Less Than or Equal to k

A common mistake is unnecessarily processing the string even when no rounds should occur.

For example:

s = "123"
k = 3

Since len(s) == k, the answer should immediately be "123".

The implementation handles this naturally because the while len(s) > k condition never executes.

Final Group Smaller Than k

The last group is not guaranteed to contain exactly k characters.

For example:

s = "12345"
k = 3

The groups become:

"123", "45"

A buggy implementation might accidentally ignore the last incomplete group or access indices out of bounds.

Our solution handles this correctly by slicing safely in Python and explicitly capping the ending index in Go.

Multi Digit Sums

A digit sum can produce more than one digit.

For example:

s = "999"
k = 2

The first round becomes:

"99" → 18
"9" → 9

Result:

"189"

An incorrect solution might assume every group produces a single digit and mishandle grouping in future rounds.

Our implementation converts every sum to its full string representation, ensuring subsequent rounds work correctly.