3498. Reverse Degree of a String

EasyStringSimulation

Leetcode Link

Problem Description

Given a string s consisting of lowercase English letters, you need to calculate its reverse degree.

The reverse degree is calculated using the following steps:

For each character in the string, determine its position in the reversed alphabet, where:
- 'a' has position 26
- 'b' has position 25
- 'c' has position 24
- ... and so on ...
- 'z' has position 1
Multiply this reversed alphabet position by the character's position in the string (using 1-based indexing, where the first character is at position 1, the second at position 2, etc.)
Sum up all these products for every character in the string.

For example, if s = "abc":

'a' is at position 1 in the string and has reversed alphabet value 26, contributing 1 × 26 = 26
'b' is at position 2 in the string and has reversed alphabet value 25, contributing 2 × 25 = 50
'c' is at position 3 in the string and has reversed alphabet value 24, contributing 3 × 24 = 72
The reverse degree would be 26 + 50 + 72 = 148

Return the calculated reverse degree of the input string s.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The problem asks us to compute a weighted sum where each character contributes based on two factors: its position in the string and its position in the reversed alphabet.

The key insight is that we need to process each character exactly once and perform a simple calculation. Since we're dealing with lowercase English letters, we can leverage the ASCII values to determine alphabet positions.

For the reversed alphabet position, we notice that:

'a' (the 1st letter) should map to 26
'b' (the 2nd letter) should map to 25
'z' (the 26th letter) should map to 1

This creates an inverse relationship. If a character is the k-th letter in the normal alphabet, its reversed position is 26 - (k - 1) or simply 27 - k.

To find k (the normal alphabet position), we can use ord(c) - ord('a') + 1. For example:

'a': ord('a') - ord('a') + 1 = 0 + 1 = 1
'b': ord('b') - ord('a') + 1 = 1 + 1 = 2

Therefore, the reversed position becomes 27 - k = 27 - (ord(c) - ord('a') + 1) = 26 - (ord(c) - ord('a')).

Once we have this formula, we simply iterate through the string, keeping track of each character's position (1-indexed), calculate the product of the string position and reversed alphabet position, and accumulate the sum. This gives us a straightforward O(n) solution with O(1) extra space.

Solution Approach

The solution follows a direct simulation approach where we iterate through the string once and calculate the reverse degree by processing each character.

Here's the step-by-step implementation:

Initialize a result variable: Start with ans = 0 to accumulate the reverse degree sum.
Iterate through the string with position tracking: Use enumerate(s, 1) to iterate through the string while getting both the character and its 1-indexed position. The 1 parameter makes the enumeration start from 1 instead of 0, which matches our requirement for 1-based indexing.
Calculate the reversed alphabet position: For each character c:
- First, find its position in the normal alphabet: ord(c) - ord('a') gives us 0 for 'a', 1 for 'b', etc.
- Then calculate the reversed position: x = 26 - (ord(c) - ord('a'))
- This gives us 26 for 'a', 25 for 'b', ..., 1 for 'z'
Compute the contribution: Multiply the character's position in the string i by its reversed alphabet value x, and add this product to our running sum: ans += i * x
Return the result: After processing all characters, return the accumulated sum.

The algorithm processes each character exactly once with constant-time operations for each character, resulting in O(n) time complexity where n is the length of the string. The space complexity is O(1) since we only use a fixed amount of extra space regardless of the input size.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with the string s = "bad":

Step 1: Initialize

ans = 0 (to accumulate our result)

Step 2: Process character 'b' at position 1

Character: 'b', String position: 1
Normal alphabet position: ord('b') - ord('a') = 98 - 97 = 1
Reversed alphabet position: x = 26 - 1 = 25
Contribution: 1 × 25 = 25
Update: ans = 0 + 25 = 25

Step 3: Process character 'a' at position 2

Character: 'a', String position: 2
Normal alphabet position: ord('a') - ord('a') = 97 - 97 = 0
Reversed alphabet position: x = 26 - 0 = 26
Contribution: 2 × 26 = 52
Update: ans = 25 + 52 = 77

Step 4: Process character 'd' at position 3

Character: 'd', String position: 3
Normal alphabet position: ord('d') - ord('a') = 100 - 97 = 3
Reversed alphabet position: x = 26 - 3 = 23
Contribution: 3 × 23 = 69
Update: ans = 77 + 69 = 146

Step 5: Return result

The reverse degree of "bad" is 146

This example demonstrates how each character's contribution is calculated by multiplying its 1-based position in the string with its reversed alphabet value, and all contributions are summed to get the final reverse degree.

Solution Implementation

1class Solution:
2    def reverseDegree(self, s: str) -> int:
3        """
4        Calculate the reverse degree of a string.
5      
6        For each character in the string, compute its "reverse position" in the alphabet
7        (where 'a' has reverse position 26, 'b' has 25, ..., 'z' has 1)
8        and multiply by its 1-indexed position in the string.
9      
10        Args:
11            s: Input string containing lowercase letters
12          
13        Returns:
14            The sum of (position * reverse_alphabet_position) for all characters
15        """
16        total_sum = 0
17      
18        # Iterate through the string with 1-indexed positions
19        for position, char in enumerate(s, 1):
20            # Calculate reverse alphabetical position
21            # 'a' -> 26, 'b' -> 25, ..., 'z' -> 1
22            reverse_alphabet_position = 26 - (ord(char) - ord('a'))
23          
24            # Add the product of position and reverse alphabet position to total
25            total_sum += position * reverse_alphabet_position
26          
27        return total_sum
28

1class Solution {
2    public int reverseDegree(String s) {
3        int stringLength = s.length();
4        int totalReverseDegree = 0;
5      
6        // Iterate through each character position (1-based indexing)
7        for (int position = 1; position <= stringLength; position++) {
8            // Get the character at current position (convert to 0-based index)
9            char currentChar = s.charAt(position - 1);
10          
11            // Calculate reverse alphabetical value (distance from 'z')
12            // 'a' = 26, 'b' = 25, ..., 'z' = 1
13            int reverseAlphabeticalValue = 26 - (currentChar - 'a');
14          
15            // Add weighted value (position * reverse value) to total
16            totalReverseDegree += position * reverseAlphabeticalValue;
17        }
18      
19        return totalReverseDegree;
20    }
21}
22

1class Solution {
2public:
3    int reverseDegree(string s) {
4        int stringLength = s.length();
5        int totalReverseDegree = 0;
6      
7        // Iterate through each character position (1-indexed)
8        for (int position = 1; position <= stringLength; ++position) {
9            // Get the character at current position (0-indexed in string)
10            char currentChar = s[position - 1];
11          
12            // Calculate reverse alphabetical value (distance from 'z')
13            // 'a' -> 26, 'b' -> 25, ..., 'z' -> 1
14            int reverseAlphabeticalValue = 26 - (currentChar - 'a');
15          
16            // Add weighted contribution: position * reverse value
17            totalReverseDegree += position * reverseAlphabeticalValue;
18        }
19      
20        return totalReverseDegree;
21    }
22};
23

1/**
2 * Calculates the reverse degree of a string based on character positions and their distance from 'z'
3 * @param s - The input string containing lowercase letters
4 * @returns The sum of weighted reverse alphabetical distances
5 */
6function reverseDegree(s: string): number {
7    // Initialize the result accumulator
8    let totalScore: number = 0;
9  
10    // Iterate through each character position (1-indexed)
11    for (let position: number = 1; position <= s.length; position++) {
12        // Get the character at current position (convert to 0-indexed)
13        const currentChar: string = s.charAt(position - 1);
14      
15        // Calculate the reverse alphabetical distance (distance from 'z')
16        // 'a' = 26, 'b' = 25, ..., 'z' = 1
17        const reverseAlphabeticalValue: number = 26 - (currentChar.charCodeAt(0) - 'a'.charCodeAt(0));
18      
19        // Add the weighted value (position * reverse alphabetical value) to the total
20        totalScore += position * reverseAlphabeticalValue;
21    }
22  
23    return totalScore;
24}
25

Time and Space Complexity

Time Complexity: O(n) where n is the length of the string s. The algorithm iterates through each character in the string exactly once using the enumerate function. For each character, it performs constant-time operations: calculating the ASCII value difference, arithmetic operations, and adding to the result. Since we visit each character once and perform O(1) work per character, the overall time complexity is linear.

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. The variables used are:

ans: a single integer to accumulate the result
i: the index variable from enumerate
c: the current character being processed
x: a temporary integer to store the calculated degree value

All these variables use constant space that doesn't scale with the input size. The enumerate function itself doesn't create a new data structure but rather returns an iterator that generates values on-the-fly, so it doesn't consume additional space proportional to the input.

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

Common Pitfalls

1. Using 0-based indexing instead of 1-based indexing

One of the most common mistakes is forgetting that the problem requires 1-based indexing for character positions in the string. Developers often default to 0-based indexing since it's the standard in most programming languages.

Incorrect approach:

for i, char in enumerate(s):  # This starts from 0
    reverse_pos = 26 - (ord(char) - ord('a'))
    total_sum += i * reverse_pos  # Wrong: uses 0-based index

Correct approach:

for i, char in enumerate(s, 1):  # Start enumeration from 1
    reverse_pos = 26 - (ord(char) - ord('a'))
    total_sum += i * reverse_pos  # Correct: uses 1-based index

2. Incorrectly calculating the reversed alphabet position

Another frequent error is miscalculating the reversed alphabet position, particularly getting the formula backwards or off by one.

Common incorrect formulas:

# Wrong: This gives 'a'->0, 'b'->1, ..., 'z'->25
reverse_pos = ord(char) - ord('a')

# Wrong: This gives 'a'->25, 'b'->24, ..., 'z'->0
reverse_pos = 25 - (ord(char) - ord('a'))

# Wrong: This gives 'a'->27, 'b'->26, ..., 'z'->2
reverse_pos = 27 - (ord(char) - ord('a'))

Correct formula:

# Correct: 'a'->26, 'b'->25, ..., 'z'->1
reverse_pos = 26 - (ord(char) - ord('a'))

3. Manual index tracking with potential off-by-one errors

Some developers might try to manually track the index, which can lead to initialization or increment errors:

Error-prone approach:

index = 0  # Wrong: should start at 1
for char in s:
    reverse_pos = 26 - (ord(char) - ord('a'))
    total_sum += index * reverse_pos
    index += 1  # Index will be 0 for first character

Better approach using enumerate:

for index, char in enumerate(s, 1):
    reverse_pos = 26 - (ord(char) - ord('a'))
    total_sum += index * reverse_pos

Prevention Tips:

Always verify your indexing against the problem examples
Test edge cases like single character strings ('a', 'z')
Double-check the reversed alphabet mapping for boundary characters
Use enumerate with the start parameter rather than manual index tracking

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: