Facebook Pixel

3838. Weighted Word Mapping

EasyArrayStringSimulation
LeetCode ↗

Problem Description

You are given an array of strings words, where each string represents a word containing lowercase English letters.

You are also given an integer array weights of length 26, where weights[i] represents the weight of the ith lowercase English letter.

The weight of a word is defined as the sum of the weights of its characters.

For each word, take its weight modulo 26 and map the result to a lowercase English letter using reverse alphabetical order (0 -> 'z', 1 -> 'y', ..., 25 -> 'a').

Return a string formed by concatenating the mapped characters for all words in order.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Simulationorstraightforward?yesFastlookup orcounting?noSimulation /Basic DSA

Direct simulation of character weight summation and modulo mapping.

Open in Flowchart

Intuition

The problem describes a direct sequence of operations to perform on each word, so we can solve it by faithfully following the steps described.

For each word, we need its weight, which is simply the sum of the weights of all its characters. Since each character c is a lowercase letter, its position in the alphabet is ord(c) - ord('a'), and we look up weights[ord(c) - ord('a')] to get its weight. Adding these up gives the total weight s of the word.

Next, we take s % 26 to bring the value into the range [0, 25]. The mapping uses reverse alphabetical order, where 0 -> 'z', 1 -> 'y', and so on up to 25 -> 'a'. Notice that the index of the target letter in normal alphabetical order is 25 - (s % 26). So we can directly use ascii_lowercase[25 - s % 26] to obtain the mapped character.

Finally, we collect the mapped character for each word in order and join them into a single string as the answer.

Solution Approach

Solution 1: Simulation

We iterate through each word w in words, calculate its weight s, which is the sum of the weights of all characters in the word. Then we calculate s modulo 26, map the result to a lowercase English letter, and finally concatenate all the mapped characters and return.

The detailed steps are as follows:

  1. Create an empty list ans to store the mapped character for each word.
  2. For each word w in words, compute its weight s = sum(weights[ord(c) - ord('a')] for c in w), where ord(c) - ord('a') gives the alphabet index of character c, which is used to look up its weight.
  3. Take s % 26 to bring the value into the range [0, 25], then map it using reverse alphabetical order. Since 0 -> 'z', 1 -> 'y', ..., 25 -> 'a', the target character is ascii_lowercase[25 - s % 26]. Append it to ans.
  4. After processing all words, join the characters in ans into a single string and return it.

The time complexity is O(L), where L is the total number of characters across all words in words. The space complexity is O(n), where n is the number of words, ignoring the space consumed by the answer string.

Example Walkthrough

Let's trace through a small example to see how the simulation approach works.

Input:

  • words = ["abc", "zz"]
  • weights is the array where weights[0] = 1 (for 'a'), weights[1] = 2 (for 'b'), weights[2] = 3 (for 'c'), ..., and weights[25] = 26 (for 'z'). In other words, weights[i] = i + 1.

We process each word in order, building up our list ans.

Step 1: Process the word "abc"

We compute the weight s by summing the weights of each character:

  • Character 'a': index is ord('a') - ord('a') = 0, so weights[0] = 1.
  • Character 'b': index is ord('b') - ord('a') = 1, so weights[1] = 2.
  • Character 'c': index is ord('c') - ord('a') = 2, so weights[2] = 3.

Total weight: s = 1 + 2 + 3 = 6.

Now take s % 26 = 6 % 26 = 6.

Map using reverse alphabetical order. The target index in normal order is 25 - 6 = 19, which corresponds to ascii_lowercase[19] = 't'.

We append 't' to ans. Now ans = ['t'].

Step 2: Process the word "zz"

We compute the weight s:

  • Character 'z': index is ord('z') - ord('a') = 25, so weights[25] = 26.
  • Character 'z': index is 25 again, so weights[25] = 26.

Total weight: s = 26 + 26 = 52.

Now take s % 26 = 52 % 26 = 0.

Map using reverse alphabetical order. The target index is 25 - 0 = 25, which corresponds to ascii_lowercase[25] = 'z'.

We append 'z' to ans. Now ans = ['t', 'z'].

Step 3: Build the result

After processing all words, we join the characters in ans:

"".join(['t', 'z']) = "tz"

Output: "tz"

This confirms the approach: for each word we sum character weights, reduce modulo 26, map through reverse alphabetical order via 25 - s % 26, and concatenate the results in order.

Solution Implementation

1from typing import List
2from string import ascii_lowercase
3
4
5class Solution:
6    def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
7        # Collect the resulting character for each word
8        result_chars = []
9
10        for word in words:
11            # Sum the weights of every character in the current word.
12            # Each character is mapped to an index 0..25 via its position in the alphabet.
13            weight_sum = sum(weights[ord(char) - ord('a')] for char in word)
14
15            # Map the total weight to a lowercase letter.
16            # Take the sum modulo 26 to keep it within the alphabet range,
17            # then mirror it (25 - index) to pick the corresponding letter from the end.
18            mapped_index = 25 - weight_sum % 26
19            result_chars.append(ascii_lowercase[mapped_index])
20
21        # Join all mapped characters into the final string.
22        return ''.join(result_chars)
23
1class Solution {
2    /**
3     * For each word, compute the sum of its characters' weights modulo 26,
4     * then map that value to a character using the formula 'a' + (25 - sum).
5     *
6     * @param words   the array of input words (assumed to contain only lowercase letters)
7     * @param weights an array of length 26 where weights[i] is the weight of ('a' + i)
8     * @return a string whose i-th character is derived from the i-th word
9     */
10    public String mapWordWeights(String[] words, int[] weights) {
11        // Accumulates the resulting characters for each word.
12        StringBuilder ans = new StringBuilder();
13
14        // Process every word independently.
15        for (String word : words) {
16            // Running sum of weights, kept within [0, 25] via modulo 26.
17            int sum = 0;
18            for (char ch : word.toCharArray()) {
19                sum = (sum + weights[ch - 'a']) % 26;
20            }
21
22            // Map the computed sum to a character: index 0 -> 'z', 25 -> 'a'.
23            ans.append((char) ('a' + (25 - sum)));
24        }
25
26        return ans.toString();
27    }
28}
29
1class Solution {
2public:
3    // Maps each word to a single character based on the weighted sum of its letters.
4    string mapWordWeights(vector<string>& words, vector<int>& weights) {
5        string result;
6        result.reserve(words.size());
7
8        for (const string& word : words) {
9            int weightedSum = 0;
10
11            // Accumulate the weight of every character, keeping the value within [0, 25].
12            for (char ch : word) {
13                weightedSum = (weightedSum + weights[ch - 'a']) % 26;
14            }
15
16            // Convert the complement of the sum (25 - sum) into a lowercase letter.
17            result.push_back(static_cast<char>('a' + (25 - weightedSum)));
18        }
19
20        return result;
21    }
22};
23
1/**
2 * Maps each word to a single character based on the cumulative weight of its letters.
3 *
4 * For every word, the weights of its characters (looked up by their position in the
5 * alphabet) are summed modulo 26. The resulting value `s` is then transformed into a
6 * letter using `25 - s`, producing one output character per input word. All these
7 * characters are concatenated to form the final result string.
8 *
9 * @param words   - The list of input words to process.
10 * @param weights - A length-26 array mapping each letter ('a'..'z') to a numeric weight.
11 * @returns A string composed of one character per input word.
12 */
13function mapWordWeights(words: string[], weights: number[]): string {
14    // Collects the single character computed for each word.
15    const result: string[] = [];
16
17    for (const word of words) {
18        // Accumulated weight for the current word, kept within [0, 25].
19        let sum = 0;
20
21        for (const char of word) {
22            // Convert the character to its alphabet index (0 for 'a', 25 for 'z'),
23            // add its weight, and wrap around using modulo 26.
24            sum = (sum + weights[char.charCodeAt(0) - 97]) % 26;
25        }
26
27        // Mirror the value within the alphabet (25 - sum) and convert back to a letter.
28        result.push(String.fromCharCode(97 + (25 - sum)));
29    }
30
31    // Join all per-word characters into the final string.
32    return result.join('');
33}
34

Time and Space Complexity

  • Time Complexity: O(L), where L is the sum of the lengths of all words in words. The outer loop iterates over each word w in words, and for each word, the inner generator expression sum(weights[ord(c) - ord('a')] for c in w) iterates over every character c in that word. Each character contributes a constant amount of work (an array lookup and an addition). Therefore, the total work is proportional to the combined length of all words, giving O(L).

  • Space Complexity: O(W), where W is the length of words. The list ans accumulates one character per word, so it holds W elements before being joined into the result string. The intermediate sum s and other variables use only O(1) additional space, so the dominant auxiliary space is the ans list of size O(W).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Mapping the modulo result in the wrong direction (forward instead of reverse alphabetical)

The most common mistake is mapping weight_sum % 26 directly to a letter using forward alphabetical order (i.e., 0 -> 'a', 1 -> 'b', ..., 25 -> 'z'), instead of the reverse order required by the problem (0 -> 'z', 1 -> 'y', ..., 25 -> 'a').

Incorrect code:

# WRONG: this maps 0 -> 'a', 1 -> 'b', ... (forward order)
mapped_index = weight_sum % 26
result_chars.append(ascii_lowercase[mapped_index])

Why it fails: For an input whose weight modulo 26 is 0, this produces 'a', but the problem clearly states 0 -> 'z'. Every character would be off, producing a completely wrong answer.

Solution: Mirror the index with 25 - (weight_sum % 26) so that 0 lands on the last letter 'z' and 25 lands on the first letter 'a'.

mapped_index = 25 - weight_sum % 26          # reverse mapping
result_chars.append(ascii_lowercase[mapped_index])

An equally valid alternative is to build the letter directly with arithmetic, which makes the reverse intent explicit:

mapped_index = weight_sum % 26
result_chars.append(chr(ord('z') - mapped_index))

Pitfall 2: Forgetting to take the modulo before mirroring (or applying modulo at the wrong place)

Because weights can be large (and even negative if the constraints allow), the raw weight_sum may fall well outside [0, 25]. Mirroring before reducing leads to an out-of-range index.

Incorrect code:

# WRONG: weight_sum can be >= 26, causing a negative or out-of-range index
mapped_index = 25 - weight_sum
result_chars.append(ascii_lowercase[mapped_index])

Why it fails: If weight_sum = 100, then 25 - 100 = -75. Python's negative indexing won't raise an error here but silently selects the wrong character, producing a hard-to-spot bug.

Solution: Always reduce with % 26 first, then mirror. Note Python's % already returns a non-negative result for negative operands, so (-3) % 26 == 23, which keeps the index valid even when negative weights are involved:

mapped_index = 25 - (weight_sum % 26)        # modulo first, then mirror

Pitfall 3: Assuming weights always has length 26

The code indexes weights[ord(char) - ord('a')], which relies on weights having exactly 26 entries. If a caller passes a shorter array, an IndexError occurs.

Solution: This is guaranteed by the problem constraints (weights has length 26), so no defensive check is strictly necessary. If writing more robust library code, you could validate the length up front:

if len(weights) != 26:
    raise ValueError("weights must have exactly 26 elements")

For a LeetCode-style submission, relying on the stated constraint and keeping the code lean is the preferred choice.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More