LeetCode Problem 3838

Difficulty: 🟢 Easy
Topics: Array, String, Simulation

Solution

Problem Understanding

The problem provides two inputs:

• words, an array of lowercase English strings.
• weights, an array of 26 integers where weights[i] represents the weight assigned to the letter corresponding to index i (0 -> 'a', 1 -> 'b', ..., 25 -> 'z').

For every word, we must compute its total weight by summing the weights of all its characters. Once we have the total weight, we take that value modulo 26.

The resulting value is then converted into a character using a reverse alphabet mapping:

Modulo Result	Character
0	z
1	y
2	x
...	...
25	a

After processing every word, we concatenate all mapped characters together and return the resulting string.

The constraints are very small. There are at most 100 words, and each word has length at most 10. Therefore, the total number of characters processed is at most 1000. This immediately suggests that a straightforward simulation solution will be efficient enough.

Some important observations and edge cases include:

• A word's weight may be much larger than 26, so taking modulo 26 is required.
• The modulo result can be 0, which must map to 'z', not 'a'.
• Every word contains only lowercase English letters, so indexing into the weights array is always safe.
• The weights array always contains exactly 26 elements.
• Single-character words should be handled exactly the same as longer words.

Approaches

Brute Force Approach

The most direct solution is to process each word independently.

For every word, iterate through all of its characters and compute the total weight by repeatedly looking up each character's assigned value in the weights array. After computing the sum, calculate sum % 26 and convert that value into the corresponding reverse-alphabet character.

Finally, append the character to the answer string.

This approach is correct because it follows the problem statement exactly. Every character contributes its assigned weight, every word is reduced modulo 26, and every modulo result is converted using the required mapping.

Given the small constraints, this solution is already fast enough.

Key Insight

There is no hidden optimization required.

The crucial observation is that the problem is simply a simulation. Each character contributes independently to the word's weight, and the reverse-alphabet mapping can be computed directly using character arithmetic.

If the modulo result is m, then:

0 -> z
1 -> y
2 -> x
...
25 -> a

This corresponds to:

'z' - m

Using ASCII arithmetic, the mapped character can be computed as:

chr(ord('z') - m)

This allows us to avoid storing an explicit lookup table.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × L)	O(1) excluding output	Directly computes each word weight character by character
Optimal	O(N × L)	O(1) excluding output	Same simulation, uses direct arithmetic for reverse mapping

Here, N is the number of words and L is the average word length.

Algorithm Walkthrough

1. Create an empty result container that will store the mapped character for each word.
2. Iterate through every word in words.
3. For the current word, initialize a variable word_weight to zero.
4. Iterate through every character in the word.
5. Convert the character into an index using:

index = ord(character) - ord('a')

This converts 'a' to 0, 'b' to 1, and so on. 6. Add weights[index] to word_weight. 7. After processing all characters in the word, compute:

remainder = word_weight % 26

8. Convert the remainder into its reverse-alphabet character:

mapped_character = chr(ord('z') - remainder)

9. Append the mapped character to the result container.
10. After all words have been processed, join the collected characters into a single string and return it.

Why it works

The algorithm computes exactly the quantity defined in the problem statement. For every word, it sums the weights of all characters, applies modulo 26, and converts the result using the required reverse-alphabet mapping. Since each step directly mirrors the specification, the produced character for every word is correct, and concatenating those characters produces the correct final answer.

Python Solution

from typing import List

class Solution:
    def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
        result = []

        for word in words:
            word_weight = 0

            for ch in word:
                word_weight += weights[ord(ch) - ord('a')]

            remainder = word_weight % 26
            result.append(chr(ord('z') - remainder))

        return "".join(result)

The implementation follows the algorithm directly.

The outer loop processes each word independently. For every word, the inner loop computes its total weight by converting each character into a zero-based alphabet index and retrieving the corresponding value from the weights array.

Once the total weight is known, the modulo operation reduces it to a value between 0 and 25. The reverse-alphabet mapping is then implemented using character arithmetic. Since 'z' corresponds to modulo value 0 and each larger modulo value moves backward through the alphabet, chr(ord('z') - remainder) produces the required character.

The collected characters are stored in a list and joined at the end for efficient string construction.

Go Solution

func mapWordWeights(words []string, weights []int) string {
	result := make([]byte, 0, len(words))

	for _, word := range words {
		wordWeight := 0

		for _, ch := range word {
			wordWeight += weights[ch-'a']
		}

		remainder := wordWeight % 26
		result = append(result, byte('z'-remainder))
	}

	return string(result)
}

The Go implementation mirrors the Python solution closely.

The result is stored as a byte slice because the output consists only of lowercase English letters. Character indexing is performed using ch - 'a', which produces values from 0 to 25.

Integer overflow is not a concern because the largest possible word weight is:

10 × 100 = 1000

which easily fits within Go's integer types.

Worked Examples

Example 1

Input

words = ["abcd", "def", "xyz"]
weights = [5,3,12,14,1,2,3,2,10,6,6,9,7,8,7,10,8,9,6,9,9,8,3,7,7,2]

Word 1: "abcd"

Character	Weight	Running Sum
a	5	5
b	3	8
c	12	20
d	14	34

34 % 26 = 8

'z' - 8 = 'r'

Result so far:

"r"

Word 2: "def"

Character	Weight	Running Sum
d	14	14
e	1	15
f	2	17

17 % 26 = 17

'z' - 17 = 'i'

Result so far:

"ri"

Word 3: "xyz"

Character	Weight	Running Sum
x	7	7
y	7	14
z	2	16

16 % 26 = 16

'z' - 16 = 'j'

Final result:

"rij"

Example 2

Input

words = ["a", "b", "c"]
weights = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

Word	Weight	Modulo	Character
a	1	1	y
b	1	1	y
c	1	1	y

Final result:

"yyy"

Example 3

Input

words = ["abcd"]

Character	Weight	Running Sum
a	7	7
b	5	12
c	3	15
d	4	19

19 % 26 = 19

'z' - 19 = 'g'

Final result:

"g"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N × L)	Every character of every word is processed exactly once
Space	O(1)	Only a few variables are used, excluding the output string

Let N be the number of words and L be the average word length. The algorithm visits each character exactly one time, so the running time is proportional to the total number of characters across all words. No auxiliary data structures that grow with input size are required, giving constant extra space usage aside from the output.

Test Cases

from typing import List

sol = Solution()

# Example 1
assert sol.mapWordWeights(
    ["abcd", "def", "xyz"],
    [5,3,12,14,1,2,3,2,10,6,6,9,7,8,7,10,8,9,6,9,9,8,3,7,7,2]
) == "rij"  # provided example

# Example 2
assert sol.mapWordWeights(
    ["a", "b", "c"],
    [1] * 26
) == "yyy"  # uniform weights

# Example 3
assert sol.mapWordWeights(
    ["abcd"],
    [7,5,3,4,3,5,4,9,4,2,2,7,10,2,5,10,6,1,2,2,4,1,3,4,4,5]
) == "g"  # provided example

# Modulo result equals 0
assert sol.mapWordWeights(
    ["a"],
    [26] + [1] * 25
) == "z"  # verifies 0 -> z mapping

# Single word, single character
assert sol.mapWordWeights(
    ["z"],
    [1] * 26
) == "y"  # smallest non-zero modulo

# Maximum length word
assert sol.mapWordWeights(
    ["aaaaaaaaaa"],
    [100] + [1] * 25
) == "n"  # large accumulated weight

# Multiple words producing different letters
assert sol.mapWordWeights(
    ["a", "aa", "aaa"],
    [1] * 26
) == "yxw"  # increasing sums

# All words map to z
assert sol.mapWordWeights(
    ["a", "b", "c"],
    [26] * 26
) == "zzz"  # modulo 0 for every word

# Mixed weights
assert sol.mapWordWeights(
    ["az"],
    [10] + [1] * 24 + [20]
) == "v"  # 30 % 26 = 4, maps to v

Test Summary

Test	Why
Example 1	Verifies the primary sample case
Example 2	Verifies uniform weights
Example 3	Verifies another provided sample
Modulo result equals 0	Ensures 0 maps to 'z'
Single word, single character	Smallest valid input size
Maximum length word	Verifies larger weight accumulation
Multiple words producing different letters	Checks repeated processing
All words map to z	Validates repeated modulo-zero behavior
Mixed weights	Verifies general correctness with custom values

Edge Cases

Modulo Result Is Zero

A common mistake is assuming that modulo result 0 should map to 'a'. The problem explicitly defines the reverse mapping, where 0 maps to 'z'. The implementation handles this correctly by using chr(ord('z') - remainder). When remainder is 0, the result is exactly 'z'.

Single Character Words

Some solutions accidentally assume every word contains multiple characters. The constraints allow words of length 1. Since the algorithm simply iterates through whatever characters are present, a single-character word naturally produces the correct weight and mapping.

Large Word Weights

A word can contain up to 10 characters, and each character weight can be as large as 100. Therefore a word weight can reach 1000. Implementations that forget the modulo operation may produce invalid character mappings. This solution always computes word_weight % 26 before converting the result into a letter, ensuring the mapped value remains within the valid range 0 through 25.

Many Words

The input may contain up to 100 words. A solution that repeatedly concatenates strings inefficiently inside a loop could incur unnecessary overhead. The implementation collects characters in a list (Python) or byte slice (Go) and constructs the final string once, which is efficient and scales cleanly within the problem constraints.