LeetCode Problem 1945 - Sum of Digits of String After Convert

LeetCode Problem 1945, titled "Sum of Digits of String After Convert", is a beginner-friendly problem that focuses on string manipulation, digit operations, and repeated transformations. The challenge helps developers practice loops, character conversion, and optimization techniques.

Problem Statement

Given a string s containing lowercase English letters and an integer k, perform the following operations:

Convert each character into its alphabetical position:
a = 1, b = 2, c = 3, ..., z = 26
Combine all converted values into a single numeric string.
Replace the string with the sum of its digits.
Repeat the digit-sum operation k times.

Return the final resulting integer.

Example

Input

s = "leetcode"
k = 2

Character Conversion

l = 12
e = 5
e = 5
t = 20
c = 3
o = 15
d = 4
e = 5

Combined numeric string:

12552031545

First Digit Sum

1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 = 33

Second Digit Sum

3 + 3 = 6

Output

Approach

1. Convert Characters into Numbers

Each character is converted using its alphabetical index:

value = ch - 'a' + 1

2. Calculate Digit Sum

Instead of building a large string, we directly calculate the sum of digits while processing each character. This reduces memory usage and improves performance.

3. Repeat the Transformation

Continue summing the digits until the transformation has been performed k times.

C++ Solution

class Solution {
public:

    int getLucky(string s, int k) {

        int sum = 0;

        // Convert characters and calculate initial digit sum
        for(char ch : s) {

            int value = ch - 'a' + 1;

            while(value > 0) {
                sum += value % 10;
                value /= 10;
            }
        }

        // Perform remaining transformations
        for(int i = 1; i < k; i++) {

            int newSum = 0;

            while(sum > 0) {
                newSum += sum % 10;
                sum /= 10;
            }

            sum = newSum;
        }

        return sum;
    }
};

Time Complexity

O(n + k)

Where:

n = length of the string
k = number of transformations

Space Complexity

O(1)

The algorithm uses constant extra memory.

Key Concepts Used

String manipulation
ASCII character conversion
Digit extraction using modulo (%)
Loop-based transformations
Optimization techniques

Conclusion

LeetCode Problem 1945 is a simple yet effective problem for improving programming fundamentals. It teaches efficient handling of strings and digit operations while encouraging optimized solutions without unnecessary memory usage.

LeetCode Problem 🔥 1945 - Sum of Digits of String After Convert

Comments