Reverse Degree of a String

Difficulty: Easy | Acceptance: 88.70% | Paid: No Topics: String, Simulation

You are given a 0-indexed string s.

The degree of a character is defined as its index in the string (0-indexed) plus 1.

The reverse degree of a character is defined as the degree of that character in the reversed string.

Return the sum of the reverse degrees of all the characters in s.

• Examples
• Constraints
• Approach 1: Iterative Simulation
• Approach 2: Mathematical Formula

Examples

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 <= 50
s consists of lowercase English letters.

Iterative Simulation

Intuition We can simulate the process by iterating through the string from the end to the beginning, effectively calculating the degree each character would have in the reversed string.

Steps

• Initialize a variable total to 0.
• Get the length n of the string.
• Iterate through the string from index 0 to n-1.
• For each character at index i, its reverse degree is n - i.
• Add this value to total.
• Return total.

class Solution:
    def calculateReverseDegree(self, s: str) -> int:
        n = len(s)
        total = 0
        for i in range(n):
            total += n - i
        return total

Complexity

• Time: O(n)
• Space: O(1)
• Notes: We iterate through the string once.

Mathematical Formula

Intuition The reverse degree of the character at index i is n - i. The sum of reverse degrees is the sum of integers from 1 to n, which can be calculated using the arithmetic series sum formula.

Steps

• Calculate the length n of the string.
• Apply the formula n * (n + 1) / 2.
• Return the result.

class Solution:
    def calculateReverseDegree(self, s: str) -> int:
        n = len(s)
        return n * (n + 1) // 2

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This is the optimal solution as it requires constant time regardless of input size.