Reverse Degree of a String

Platform: LeetCode
Difficulty Level: Easy
Link: reverse degree of a string

Problem

Input

• s: string

Goal

• Return reverse degree of s

Constraints

• 1 <= s.length <= 1000
• s contains only lowercase english letters

Concept

Consider alphabet positions:
a = 1, b = 2, c = 3, d = 4, e = 5. . . . . . x = 24, y = 25, z = 26.

Consider reversed alphabet positions:
a = 26, b = 25, c = 24, d = 23, e = 22 . . . . . . x = 3, y = 2, z = 1.

Consider 1-indexed string:
s = ‘abc’
Index: a -> 1, b -> 2, c -> 3

Reverse Degree of string is the sum of the products of reversed alphabet position and position in the string.

So Reverse Degree of s is:

Here,
$n$ -> length of the string
$i$ -> position of the character in the string
$\mathrm{pos}(s_i)$ -> postion of the character in the alphabet series
$(27 - \mathrm{pos}(s_i))$ -> position of the character in the reverse alphabet series

For s = ‘abc’,
ReverseDegree = 1 * (27 - 1) + 2 * (27 - 2) + 3 * (27 - 3) = 26 + 50 + 72 = 148

Examples

Example 1:

Input: s = “abc”

Output: 148

Example 2:

Input: s = “zaza”

Output: 160

Solution

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

        for i in range(len(s)):
            pos_str = i + 1 # here i starts from 0
            pos_rev_series = 27 - (ord(s[i]) - 96)
            
            rd = rd + pos_str * pos_rev_series
        
        return rd

func reverseDegree(s string) int {
    rd := 0

    for i, char := range s {
        posStr := i + 1 // i starts from 0
        posRevSeries := 27 - (int(char) - 96)

        rd = rd + posStr * posRevSeries
    }

    return rd
}

Considering the constraint that the string will only contain lowercase english letters a-z, the ASCII values will be in the range [97, 122].

Subtracting 96 from the ASCII values,
a = 97 - 96 = 1, b = 98 - 96 = 2, c = 99 - 96 = 3, …… y = 121 - 96 = 25, z = 122 - 96 = 26
This will give us the positions in the range [1, 26].

Since we want the positions in reverse order, we subtract the positions from 27.
a = 27 - 1 = 26, b = 27 - 2 = 25, c = 27 - 3 = 24, …… y = 27 - 25 = 2, z = 27 - 1 = 26
This will give the position in the range [26, 1].

Complexity Analysis

Let n be the length of the string.

Time

• traversing the characters of the string once = $O(n)$

Time = $O(n)$

Space

• no extra space used

Space = $O(1)$

Comments

• Important part here is to understand ASCII values.