2243. Calculate Digit Sum of a String
EasyView on LeetCode
Problem Overview
The string is repeatedly rewritten until its length is at most k.
Intuition
The string is repeatedly rewritten until its length is at most k. In one round it is cut into consecutive blocks of size k, with a shorter final block when the length is not a multiple of k. Each block is replaced by the decimal representation of the sum of its digits. Because a sum of at most k nines is a short number, the new string is shorter than the old one whenever the old length exceeded k, so the process ends quickly. The final string is the answer. Simulation is enough: every character of the current string must be read in each round.
Algorithm
- 1While the current string is longer than k, prepare a fresh builder.
- 2Walk the string in steps of k. For each block, add its digit values and append that sum as text.
- 3Replace the current string with the builder contents and repeat.
- 4Return the string once its length is at most k.
Example Walkthrough
Input: s = "11111222223", k = 3
- 1.The first round groups as 111, 112, 222, 23 and rewrites them as 3, 4, 6, 5, so the string becomes 3465.
- 2.The next round groups as 346 and 5, which become 13 and 5, so the string becomes 135.
- 3.The length is now 3, which equals k, so the process stops at 135.
Output: 135
Common Pitfalls
- •Append the full decimal form of each group sum. A sum of 10 or more contributes more than one character.
- •The final block may be shorter than k when the length is not divisible by k. Still sum every remaining digit.
- •Stop when the length is less than or equal to k. Do not run one more unnecessary round.
- •Each round builds a new string. Reusing the old buffer without clearing it would mix rounds.
2243.cs
C#
// Approach: While the string is longer than k, split it into consecutive
// groups of at most k digits, replace each group with the decimal digits of
// its sum, and repeat on that shorter string. The process stops once the
// length is at most k. Every character of the current string must be read
// each round, so the simulation is already tight.
// Time: O(n) across shrinking rounds Space: O(n)
using System.Text;
public class Solution
{
public string DigitSum(string s, int k)
{
while (s.Length > k)
{
var sb = new StringBuilder();
for (int i = 0; i < s.Length; i += k)
{
int sum = 0;
int end = Math.Min(s.Length, i + k);
for (int j = i; j < end; ++j)
sum += s[j] - '0';
sb.Append(sum);
}
s = sb.ToString();
}
return s;
}
}
Was this solution helpful?
Related Problems
- 68. Text Justification(Hard)
- 592. Fraction Addition and Subtraction(Unknown)
- 657. Robot Return to Origin(Unknown)
- 838. Push Dominoes(Medium)
- 1545. Find Kth Bit in Nth Binary String(Easy)
- 1598. Crawler Log Folder(Easy)