Reverse Degree of a String

Easy

#3110Time: O(N), where N is the length of the string `s`. Populating the map takes constant time O(1) as the alphabet size is fixed at 26. The main part of the algorithm is the loop that iterates through the string once.Space: O(1). We use a HashMap to store the values for the 26 lowercase English letters. Since the size of the alphabet is constant, the space required for the map does not grow with the input string size.1 company

Data structures

String

Companies

Capgemini

Prompt

Given a string s, calculate its reverse degree.

The reverse degree is calculated as follows:

For each character, multiply its position in the reversed alphabet ('a' = 26, 'b' = 25, ..., 'z' = 1) with its position in the string (1-indexed).
Sum these products for all characters in the string.

Return the reverse degree of s.

Example 1:

Input: s = "abc"

Output: 148

Explanation:

Letter	Index in Reversed Alphabet	Index in String	Product
`'a'`	26	1	26
`'b'`	25	2	50
`'c'`	24	3	72

The reversed degree is 26 + 50 + 72 = 148.

Example 2:

Input: s = "zaza"

Output: 160

Explanation:

Letter	Index in Reversed Alphabet	Index in String	Product
`'z'`	1	1	1
`'a'`	26	2	52
`'z'`	1	3	3
`'a'`	26	4	104

The reverse degree is 1 + 52 + 3 + 104 = 160.

Constraints:

1 <= s.length <= 1000
s contains only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves pre-calculating the reverse alphabetical value for each character and storing them in a HashMap. We then iterate through the input string, and for each character, we look up its value in the map, multiply it by its 1-indexed position, and add the result to a running total.

Algorithm

Initialize a HashMap<Character, Integer>.
Populate the map by iterating from 'a' to 'z', mapping each character c to its value 26 - (c - 'a').
Initialize a sum variable reverseDegree to 0.
Loop through the input string s from index i = 0 to s.length() - 1.
Inside the loop, get the character currentChar and retrieve its value from the map.
Multiply the character's value by its 1-indexed position (i + 1).
Add the product to reverseDegree.
Return reverseDegree after the loop.

Walkthrough

In this method, we first set up a helper data structure, a HashMap, to act as a lookup table. This map stores each lowercase letter and its corresponding reverse alphabetical value. For example, 'a' maps to 26, 'b' to 25, and so on. Once the map is populated, we process the input string. We iterate through the string character by character, using the character's 1-indexed position. For each character, we fetch its pre-calculated value from the map, multiply it by its position, and accumulate the result in a total sum. This separation of concerns can make the code's intent clearer, though it comes at the cost of extra space and minor performance overhead.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int reverseDegree(String s) {6        Map<Character, Integer> alphabetValues = new HashMap<>();7        for (char c = 'a'; c <= 'z'; c++) {8            alphabetValues.put(c, 26 - (c - 'a'));9        }10 11        int reverseDegree = 0;12        for (int i = 0; i < s.length(); i++) {13            char currentChar = s.charAt(i);14            int charValue = alphabetValues.get(currentChar);15            int position = i + 1;16            reverseDegree += charValue * position;17        }18        return reverseDegree;19    }20}

Complexity

Time

O(N), where N is the length of the string `s`. Populating the map takes constant time O(1) as the alphabet size is fixed at 26. The main part of the algorithm is the loop that iterates through the string once.

Space

O(1). We use a HashMap to store the values for the 26 lowercase English letters. Since the size of the alphabet is constant, the space required for the map does not grow with the input string size.

Trade-offs

Pros

The logic is very explicit, making the code easy to read and understand.
Separates the concern of calculating character values from the main summation logic.

Cons

Uses extra space for the HashMap.
Slightly less performant due to the overhead of hash calculations and map lookups compared to direct arithmetic calculation.

This is the most efficient approach. It involves a single loop through the string. In each iteration, we calculate the character's reverse alphabetical value on-the-fly using a simple arithmetic formula and multiply it by its 1-indexed position. This avoids the need for any extra data structures.

Algorithm

Initialize a sum variable reverseDegree to 0.
Iterate through the input string s using an index i from 0 to s.length() - 1.
In each iteration, get the character currentChar = s.charAt(i).
Calculate its reverse alphabetical value directly using the formula 26 - (currentChar - 'a').
Multiply the calculated value by the 1-indexed position (i + 1).
Add the result to reverseDegree.
After the loop completes, return the final reverseDegree.

Walkthrough

This optimal solution processes the string in a single pass without any auxiliary data structures. We iterate through the string, and for each character, we perform the required calculations directly. The key is the formula 26 - (c - 'a'), which efficiently converts any lowercase character c to its reverse alphabetical value. This value is then multiplied by the character's 1-indexed position in the string. The product is added to a running total. This method is highly efficient as it minimizes both space usage and computational overhead, performing only essential arithmetic operations within the loop.

1class Solution {2    public int reverseDegree(String s) {3        int reverseDegree = 0;4        for (int i = 0; i < s.length(); i++) {5            char currentChar = s.charAt(i);6            // 'a' -> 26, 'b' -> 25, ..., 'z' -> 17            // This can be calculated as 26 - (currentChar - 'a')8            int charValue = 26 - (currentChar - 'a');9            int position = i + 1;10            reverseDegree += charValue * position;11        }12        return reverseDegree;13    }14}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string exactly once, performing a constant amount of work for each character.

Space

O(1). We only use a few variables to store the running total and the loop index. The space required is constant and does not depend on the size of the input string.

Trade-offs

Pros

Optimal time and space complexity.
No overhead from creating and using extra data structures.
Concise and efficient implementation.

Cons

The formula 26 - (c - 'a') might be slightly less immediately obvious to a reader unfamiliar with character arithmetic, but it is a common pattern.

Solutions

Solution

1class Solution {2public3  int reverseDegree(String s) {4    int n = s.length();5    int ans = 0;6    for (int i = 1; i <= n; ++i) {7      int x = 26 - (s.charAt(i - 1) - 'a');8      ans += i * x;9    }10    return ans;11  }12}

1class Solution:2    def reverseDegree(self, s: str) -> int: ans = 0 for i, c in enumerate(s, 1): x = 26 - (ord(c) - ord("a")) ans += i * x return ans

1class Solution {2public:3  int reverseDegree(string s) {4    int n = s.length();5    int ans = 0;6    for (int i = 1; i <= n; ++i) {7      int x = 26 - (s[i - 1] - 'a');8      ans += i * x;9    }10    return ans;11  }12};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem