Intuition¶

The problem requires converting each character of a string into its corresponding digit(s) based on its position in the alphabet. My initial thought was to sum these digits and then iteratively sum the digits of the result for a given number of iterations, k. This problem combines aspects of basic character manipulation and number theory.

Approach¶

Character to Digit Conversion: Start by converting each character in the string to its position in the alphabet (a = 1, b = 2, ..., z = 26). Since some of these positions are two digits (10-26), break them down into individual digits and sum them.
Iterative Summing: After obtaining the initial sum, iteratively sum the digits of the result k-1 times. Each iteration reduces the sum further until the final single-digit sum is obtained after all iterations.
Edge Cases: Handle cases where the string might be empty (although not explicitly stated, usually strings are assumed non-empty) or when k is 1, in which case the sum from the first step is returned directly.

Complexity¶

Time complexity:
The time complexity of converting each character and summing the digits is $O(n)$, where n is the length of the string.
Each subsequent digit sum operation has a time complexity of $O(\log(sum))$, repeated k-1 times. Since log(sum) is relatively small compared to n, the overall complexity is approximately $O(n \cdot k)$.
Space complexity:
The space complexity is $O(1)$ since we are only using a fixed amount of extra space for storing the sum and other temporary variables.

Code¶

class Solution {
    public int getLucky(String s, int k) {
        int sum = 0;

        for (char ch : s.toCharArray()) {
            int value = ch - 'a' + 1;
            sum += value / 10 + value % 10;
        }

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

        return sum;
    }
}