LeetCode 3110 - Score of a String

LeetCode Problem 3110

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

This problem asks us to compute the score of a string, where the score is defined as the sum of the absolute differences of ASCII values of consecutive characters in the string. In other words, for a string s of length n, the score is calculated as:

$$\text{score}(s) = |s[0] - s[1]| + |s[1] - s[2]| + \dots + |s[n-2] - s[n-1]|$$

The input is a string s consisting only of lowercase English letters, with a length between 2 and 100. The output is a single integer representing the score of the string.

Key points are that we always have at least two characters, so there is always at least one difference to compute, and all characters are lowercase letters, so ASCII values are in the range 97 ('a') to 122 ('z'). Edge cases to consider include strings where all characters are the same (score 0), strings with alternating high and low ASCII values, and very short strings of length 2.

Approaches

The brute-force approach here is effectively the optimal approach due to the simplicity of the problem. We iterate through the string from the first character to the second-to-last character, compute the absolute difference between each character and the next, and sum these differences. This approach works correctly because it directly follows the problem statement. There is no more optimal approach because the problem requires examining each adjacent pair exactly once.

Comparison Table

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through the string once, compute absolute differences, and sum them.
Optimal	O(n)	O(1)	Same as brute force; no further optimization possible due to linear dependence on input size.

Algorithm Walkthrough

1. Initialize a variable score to 0. This variable will accumulate the sum of absolute differences.
2. Iterate through the string using an index i from 0 to len(s) - 2. Each iteration considers the character at i and the character at i + 1.
3. For each pair of adjacent characters, compute the ASCII difference using the built-in ord function in Python or direct casting in Go. Take the absolute value of the difference.
4. Add the absolute difference to the score variable.
5. After completing the iteration, return the score as the result.

Why it works: The algorithm follows the problem definition directly. Each adjacent character pair is considered exactly once, and the absolute difference is accumulated. The invariant is that after processing i characters, score contains the correct sum of absolute differences for all pairs up to index i.

Python Solution

class Solution:
    def scoreOfString(self, s: str) -> int:
        score = 0
        for i in range(len(s) - 1):
            score += abs(ord(s[i]) - ord(s[i + 1]))
        return score

The Python implementation initializes score to 0, iterates through the string indices, calculates the absolute difference between consecutive characters using ord, and adds this to score. Finally, it returns the accumulated score.

Go Solution

func scoreOfString(s string) int {
    score := 0
    for i := 0; i < len(s)-1; i++ {
        diff := int(s[i]) - int(s[i+1])
        if diff < 0 {
            diff = -diff
        }
        score += diff
    }
    return score
}

In Go, we initialize score to 0 and iterate through the string with indices. We cast characters to int to compute the ASCII difference, take the absolute value manually, and add it to score. Finally, we return the score. Go does not have a built-in abs function for integers in the standard library, so we handle the absolute value with a conditional.

Worked Examples

Example 1: s = "hello"

| i | s[i] | s[i+1] | |s[i]-s[i+1]| | score |

|---|---|---|---|---|

| 0 | 'h' (104) | 'e' (101) | 3 | 3 |

| 1 | 'e' (101) | 'l' (108) | 7 | 10 |

| 2 | 'l' (108) | 'l' (108) | 0 | 10 |

| 3 | 'l' (108) | 'o' (111) | 3 | 13 |

Final score: 13

Example 2: s = "zaz"

| i | s[i] | s[i+1] | |s[i]-s[i+1]| | score |

|---|---|---|---|---|

| 0 | 'z' (122) | 'a' (97) | 25 | 25 |

| 1 | 'a' (97) | 'z' (122) | 25 | 50 |

Final score: 50

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through each character once, performing O(1) operations per character.
Space	O(1)	Only a single integer variable is used for accumulation; no extra data structures.

The complexity is linear in the length of the string, which is acceptable given the constraints of 2 <= n <= 100.

Test Cases

# Provided examples
assert Solution().scoreOfString("hello") == 13  # Example 1
assert Solution().scoreOfString("zaz") == 50    # Example 2

# Edge cases
assert Solution().scoreOfString("aa") == 0       # All characters same
assert Solution().scoreOfString("az") == 25      # Two extreme characters
assert Solution().scoreOfString("abcdefghijklmnopqrstuvwxyz") == 25*25  # Increasing sequence

# Random cases
assert Solution().scoreOfString("abcdeedcba") == 20
assert Solution().scoreOfString("mnop") == 3
assert Solution().scoreOfString("zzzzzz") == 0

Test	Why
"hello"	Validates the example with mixed ASCII differences
"zaz"	Validates alternating high-low pattern
"aa"	Edge case with all characters identical
"az"	Edge case with maximum ASCII difference for two characters
"abcdefghijklmnopqrstuvwxyz"	Validates longer sequence with incremental differences
"abcdeedcba"	Tests symmetry in string differences
"mnop"	Small string with consecutive letters
"zzzzzz"	Repeated same character, should result in 0

Edge Cases

One important edge case is a string where all characters are identical. Here, every difference is zero, so the score must be zero. Another edge case is a string of length 2, the minimum allowed by constraints, which tests that the function handles very short input correctly. A third edge case is strings with alternating low and high ASCII values like "azazaz", which can stress the absolute difference computation and ensure correct accumulation of multiple large differences. All these cases are correctly handled by iterating through adjacent pairs and summing the absolute differences.