Reverse Degree of a String — Solution in Python, Java & C++
Reverse Degree of a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Reverse Degree of a String is an easy coding problem on strings and simulation, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Strings, Simulation
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of lowercase letters.
In the reversed alphabet 'a' has position 26, 'b' has 25, …, and 'z' has 1. The reverse degree of s is the sum, over every index i (counted from 1), of the reversed-alphabet position of s[i] multiplied by i.
Return the reverse degree of s.
Example 1
Input: s = "abc"
Output: 148
Explanation: 26 * 1 + 25 * 2 + 24 * 3 = 26 + 50 + 72 = 148.
Example 2
Input: s = "zaza"
Output: 160
Explanation: 1 * 1 + 26 * 2 + 1 * 3 + 26 * 4 = 160.
Example 3
Input: s = "z"
Output: 1
Constraints
1 <= s.length <= 1000s consists only of lowercase English letters
Hints for Reverse Degree of a String
Hint 1
The reversed-alphabet position of a letter
cis26 - (c - 'a').Hint 2
Multiply it by the 1-based index and add everything up in one pass. The largest total,
26 * (1 + 2 + … + 1000), fits in a 32-bit integer.
How to solve Reverse Degree of a String
Each character contributes independently: its reversed position times its 1-based index. One pass sums the contributions.
Approach
- Set
total = 0. - For
i = 0 .. n - 1, add(26 - (s[i] - 'a')) * (i + 1). - Return
total.
Why it works
This is the definition term by term; the bound 26 * 1000 * 1001 / 2 = 13,013,000 keeps it inside int32.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Indices are 1-based in the formula — multiply by
i + 1in a 0-based loop. 'a'is worth 26 and'z'is worth 1, not the other way round.
Reference solution
Python
def reverseDegree(s: str) -> int:
return sum((26 - (ord(c) - 97)) * (i + 1) for i, c in enumerate(s))Java
public static int reverseDegree(String s) {
int total = 0;
for (int i = 0; i < s.length(); i++) total += (26 - (s.charAt(i) - 'a')) * (i + 1);
return total;
}C++
int reverseDegree(string s) {
int total = 0;
for (int i = 0; i < (int) s.size(); i++) total += (26 - (s[i] - 'a')) * (i + 1);
return total;
}JavaScript
var reverseDegree = function(s) {
var total = 0;
for (var i = 0; i < s.length; i++) total += (26 - (s.charCodeAt(i) - 97)) * (i + 1);
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings