LeetCode Problem 3498

Difficulty: 🟢 Easy
Topics: String, Simulation

Solution

LeetCode 3498 - Reverse Degree of a String

Problem Understanding

The problem asks us to compute a special value called the reverse degree of a string.

Normally, letters are assigned positions in the alphabet as:

• 'a' = 1
• 'b' = 2
• ...
• 'z' = 26

However, this problem uses the reversed alphabet order, where:

• 'a' = 26
• 'b' = 25
• ...
• 'z' = 1

For every character in the string, we must:

1. Determine its value in the reversed alphabet.
2. Determine its position in the string, using 1-based indexing.
3. Multiply these two values together.
4. Add the result to a running total.

The final sum is the reverse degree of the string.

For example, if the character is 'b' at position 2, then:

• Reverse alphabet value = 25
• String position = 2
• Contribution = 25 × 2 = 50

The input consists of a single string s containing only lowercase English letters. The output is a single integer representing the reverse degree.

The constraints are very small:

• The string length is at most 1000.
• Only lowercase letters appear.

These constraints tell us that even a straightforward linear scan will be more than fast enough.

Important edge cases include strings of length 1, strings containing only 'a', strings containing only 'z', and strings with repeated characters. The problem guarantees that every character is a lowercase English letter, so we never need to handle invalid input or uppercase letters.

Approaches

Brute Force Approach

A brute force solution would explicitly construct the reversed alphabet mapping:

a -> 26
b -> 25
...
z -> 1

This could be stored in a hash map or dictionary. Then we would iterate through the string, look up each character's reverse value from the map, multiply it by its 1-based position, and add it to the answer.

This approach is correct because it directly follows the problem definition. However, creating and storing an entire mapping is unnecessary because there is a simple mathematical relationship between a character and its reverse-alphabet value.

Key Observation

The normal alphabet position of a character is:

ord(c) - ord('a') + 1

The reverse-alphabet value can therefore be computed directly as:

26 - (ord(c) - ord('a'))

or equivalently:

ord('z') - ord(c) + 1

This allows us to compute each character's contribution in constant time without any extra data structure.

We simply scan the string once, calculate each character's reverse value, multiply by its position, and accumulate the result.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(26)	Uses an explicit character-to-value mapping
Optimal	O(n)	O(1)	Computes reverse values directly with arithmetic

Algorithm Walkthrough

1. Initialize a variable total to 0. This will store the final reverse degree.
2. Iterate through the string using both the character and its index.
3. Convert the zero-based index into a one-based position by adding 1.
4. Compute the reverse-alphabet value of the current character using:

ord('z') - ord(character) + 1

This gives:

• 'a' → 26
• 'b' → 25
• ...
• 'z' → 1

5. Multiply the reverse value by the character's position in the string.
6. Add this product to total.
7. After processing all characters, return total.

Why it works

For every character, the algorithm computes exactly the quantity required by the problem:

(reverse alphabet value) × (1-based position)

The final answer is defined as the sum of these values over all characters. Since the algorithm computes every contribution exactly once and adds them together, the resulting total is precisely the reverse degree of the string.

Problem Understanding

The problem asks us to compute the reverse degree of a string s. In more concrete terms, each character in the string is mapped to its position in a reversed alphabet, where 'a' corresponds to 26, 'b' to 25, …, and 'z' to 1. Then, for each character, we multiply this reversed alphabet position by the character’s position in the string itself, where the string positions are 1-indexed. Summing these products for all characters in the string produces the final reverse degree.

The input is a lowercase English string of length up to 1000 characters. The output is a single integer representing the computed reverse degree. Constraints guarantee that the input contains only lowercase letters, so we do not need to handle uppercase letters or non-alphabetic characters. Important edge cases include the smallest string length (s.length = 1) and strings composed entirely of 'a' or 'z', which correspond to extreme values in the reversed alphabet mapping.

Approaches

A straightforward approach is to iterate through the string, compute the reversed alphabet index for each character, multiply it by the character’s 1-based index, and sum all these products. This brute-force method works correctly because each multiplication and sum directly follows the problem’s definition. Its time complexity is linear in the length of the string, which is acceptable for n ≤ 1000, so in fact the naive solution is already efficient.

The key observation for optimization is that the reversed alphabet index can be computed efficiently using a constant-time formula: reversed_index = 26 - (ord(char) - ord('a')). This avoids manually storing a mapping table, though it is equivalent in asymptotic complexity. No further optimization is needed, since iterating over the string is already O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through string, compute reversed index, multiply by position, sum
Optimal	O(n)	O(1)	Same as brute force, but uses a direct arithmetic formula for reversed alphabet

Algorithm Walkthrough

1. Initialize an integer variable total to 0. This will accumulate the sum of products.
2. Iterate over the string s using a 0-based index i and character ch.
3. For each character, compute its reversed alphabet index using rev_idx = 26 - (ord(ch) - ord('a')).
4. Multiply the reversed index by the character’s 1-based position i + 1.
5. Add the product to total.
6. After the loop completes, return total.

Why it works: At each step, we maintain the invariant that total equals the sum of the products of the reversed alphabet indices and the 1-based positions for all characters processed so far. Since each step directly implements the problem definition, the final value of total is guaranteed to be the correct reverse degree.

Python Solution

class Solution:
    def reverseDegree(self, s: str) -> int:
        total = 0

        for index, ch in enumerate(s, start=1):
            reverse_value = ord('z') - ord(ch) + 1
            total += reverse_value * index

        return total

The implementation follows the algorithm directly. The variable total stores the running answer. Using enumerate(s, start=1) conveniently provides the required 1-based positions. For each character, we compute its reverse-alphabet value using ASCII arithmetic and multiply it by its position. The contribution is added to total, and after the loop completes, the accumulated sum is returned. for i, ch in enumerate(s): rev_idx = 26 - (ord(ch) - ord('a')) total += rev_idx * (i + 1) return total

The code initializes a running sum `total` and iterates through the string with `enumerate`, which provides both the index and the character. The reversed alphabet index is calculated using the arithmetic formula, then multiplied by the 1-based position `(i + 1)`, and added to `total`. The sum is returned after processing all characters.

## Go Solution

```go
func reverseDegree(s string) int {
    total := 0

    for i, ch := range s {
        position := i + 1
        reverseValue := int('z'-ch) + 1
        total += reverseValue * position
    }

    for i, ch := range s {
        revIdx := 26 - int(ch-'a')
        total += revIdx * (i + 1)
    }
    return total
}

The Go implementation is nearly identical to the Python version. The range loop provides both the index and character. Since the input contains only lowercase English letters, each character occupies a single byte, and the byte index corresponds directly to the character position. The reverse value is computed using character arithmetic, accumulated into total, and returned at the end.

Worked Examples

Example 1

Input:

s = "abc"

Position	Character	Reverse Value	Contribution	Running Total
1	a	26	26 × 1 = 26	26
2	b	25	25 × 2 = 50	76
3	c	24	24 × 3 = 72	148

Final answer:

148

Example 2

Input:

s = "zaza"

Position	Character	Reverse Value	Contribution	Running Total
1	z	1	1 × 1 = 1	1
2	a	26	26 × 2 = 52	53
3	z	1	1 × 3 = 3	56
4	a	26	26 × 4 = 104	160

Final answer:

160

In Go, the iteration uses range to obtain the index and rune. The reversed alphabet index is computed by converting the rune difference to an integer. The multiplication and accumulation follow the same logic as Python. Go handles empty strings naturally (the loop does not execute), and integer arithmetic is safe for the input constraints.

Worked Examples

Example 1: s = "abc"

i	ch	rev_idx	i+1	product	total
0	a	26	1	26	26
1	b	25	2	50	76
2	c	24	3	72	148

Result: 148

Example 2: s = "zaza"

i	ch	rev_idx	i+1	product	total
0	z	1	1	1	1
1	a	26	2	52	53
2	z	1	3	3	56
3	a	26	4	104	160

Result: 160

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs a single pass through the string. Every iteration involves only constant-time arithmetic operations. No auxiliary data structures proportional to the input size are allocated, so the space complexity remains constant. | Time | O(n) | Single pass through string of length n, constant-time computation per character | | Space | O(1) | Only integer accumulator used, no additional data structures needed |

Iterating through the string dominates the runtime, and no auxiliary space grows with input size.

Test Cases

sol = Solution()

assert sol.reverseDegree("abc") == 148  # provided example
assert sol.reverseDegree("zaza") == 160  # provided example

assert sol.reverseDegree("a") == 26  # single highest reverse value
assert sol.reverseDegree("z") == 1  # single lowest reverse value

assert sol.reverseDegree("aa") == 78  # repeated maximum-value character
assert sol.reverseDegree("zz") == 3  # repeated minimum-value character

assert sol.reverseDegree("az") == 28  # opposite extremes
assert sol.reverseDegree("za") == 53  # order matters

assert sol.reverseDegree("m") == 14  # middle alphabet character

assert sol.reverseDegree("abcdefghijklmnopqrstuvwxyz") == sum(
    (26 - i) * (i + 1)
    for i in range(26)
)  # full alphabet

assert sol.reverseDegree("bbbb") == 25 * (1 + 2 + 3 + 4)  # repeated character

assert sol.reverseDegree("leetcode") == (
    15 * 1 +
    22 * 2 +
    22 * 3 +
    7 * 4 +
    25 * 5 +
    12 * 6 +
    22 * 7 +
    23 * 8
)  # general mixed string

Test Summary

Test	Why
"abc"	Verifies the first provided example
"zaza"	Verifies the second provided example
"a"	Smallest length, maximum reverse value
"z"	Smallest length, minimum reverse value
"aa"	Repeated maximum-value character
"zz"	Repeated minimum-value character
"az"	Tests opposite alphabet extremes
"za"	Confirms position weighting matters
"m"	Tests a middle alphabet letter
"abcdefghijklmnopqrstuvwxyz"	Covers every lowercase letter
"bbbb"	Repeated identical characters
"leetcode"	General realistic input

Edge Cases

Single Character String

The smallest valid input has length 1. A common mistake is to accidentally use zero-based indexing when computing contributions. For example, if "a" were assigned position 0, the answer would incorrectly become 0. The implementation avoids this by using 1-based positions via enumerate(..., start=1) in Python and i + 1 in Go.

Characters at Alphabet Extremes

The letters 'a' and 'z' represent the largest and smallest reverse values respectively. It is easy to accidentally reverse the formula and compute normal alphabet positions instead. The expression:

ord('z') - ord(ch) + 1

correctly maps 'a' to 26 and 'z' to 1, ensuring extreme cases are handled properly.

Repeated Characters

Strings such as "aaaa" or "zzzz" can expose bugs where position weighting is ignored. Even though every character has the same reverse value, each occurrence contributes a different amount because the position changes. The implementation multiplies every reverse value by its corresponding 1-based index, ensuring each occurrence contributes correctly.

Maximum Length Input

The string length can reach 1000 characters. Although this is small, the algorithm still scales efficiently because it processes each character exactly once. The time complexity remains O(n), and only a constant amount of additional memory is used regardless of string length.

Provided examples

assert Solution().reverseDegree("abc") == 148 # basic sequence assert Solution().reverseDegree("zaza") == 160 # alternating extremes

Edge cases

assert Solution().reverseDegree("a") == 26 # single character, largest reverse index assert Solution().reverseDegree("z") == 1 # single character, smallest reverse index assert Solution().reverseDegree("aaaa") == 261 + 262 + 263 + 264 # repeated max assert Solution().reverseDegree("zzzz") == 11 + 12 + 13 + 14 # repeated min assert Solution().reverseDegree("abcdefghijklmnopqrstuvwxyz") == sum((26-i)(i+1) for i in range(26)) # full alphabet assert Solution().reverseDegree("mnop") == sum((26-(ord(ch)-ord('a')))(i+1) for i,ch in enumerate("mnop")) # random subset

| Test | Why |
| --- | --- |
| `"abc"` | Basic ascending letters |
| `"zaza"` | Alternating letters with extremes |
| `"a"` | Single letter, max reverse index |
| `"z"` | Single letter, min reverse index |
| `"aaaa"` | Repeated letters at start of alphabet |
| `"zzzz"` | Repeated letters at end of alphabet |
| `"abcdefghijklmnopqrstuvwxyz"` | Full alphabet, increasing positions |
| `"mnop"` | Random subset to check general correctness |

## Edge Cases

One important edge case is a **single-character string**. Here, the loop executes once, and the formula must correctly handle the 1-based index. Both `'a'` and `'z'` represent extreme reversed indices, which tests proper arithmetic handling.

Another edge case is a **string of repeated characters**, such as `"aaaa"` or `"zzzz"`. This ensures that the multiplication by position works correctly and the summation does not accidentally overwrite previous results.

A third edge case is a **string containing letters at both extremes of the reversed alphabet**, e.g., `"zaza"`. This tests that the formula `26 - (ord(ch) - ord('a'))` correctly maps both ends and that accumulation sums correctly without integer overflow. Given the constraints, Python integers and Go `int` are sufficient for these calculations.