You are given a string s. The score of a string is defined as the sum of the absolute difference between the ASCII values of adjacent characters.
Return the score of s.
Example 1:
Input: s = "hello"
Output: 13
Explanation:
The ASCII values of the characters in s are: 'h' = 104, 'e' = 101, 'l' = 108, 'o' = 111. So, the score of s would be |104 - 101| + |101 - 108| + |108 - 108| + |108 - 111| = 3 + 7 + 0 + 3 = 13.
Example 2:
Input: s = "zaz"
Output: 50
Explanation:
The ASCII values of the characters in s are: 'z' = 122, 'a' = 97. So, the score of s would be |122 - 97| + |97 - 122| = 25 + 25 = 50.
Constraints:
2 <= s.length <= 100s consists only of lowercase English letters.Problem Overview: You are given a string s. The score of the string is the sum of the absolute differences between the ASCII values of every pair of adjacent characters. Iterate through the string, compare s[i] with s[i+1], compute abs(ord(s[i]) - ord(s[i+1])), and accumulate the result.
Approach 1: Iterative ASCII Difference Calculation (O(n) time, O(1) space)
The most direct solution scans the string once and compares each character with its neighbor. For each index i, compute the absolute difference between the ASCII values of s[i] and s[i+1]. Add this difference to a running total. Since each character is processed exactly once, the algorithm runs in O(n) time and uses O(1) extra space.
This approach relies on basic operations on a string: indexing and ASCII conversion. The key insight is that the score depends only on adjacent pairs, so no additional data structures are required. This makes it optimal for both runtime and memory usage. In practice, this is the implementation most developers use in interviews and production code because it is simple, readable, and efficient.
Approach 2: Recursive ASCII Difference Calculation (O(n) time, O(n) space)
The same logic can be expressed recursively. Define a recursive function that processes the first pair of characters, adds their ASCII difference, and then calls itself on the remainder of the string. Each call handles one adjacent pair and delegates the rest of the work to the next recursive step.
Although the algorithm still evaluates each pair exactly once (giving O(n) time complexity), recursion introduces a call stack that grows with the string length. This results in O(n) auxiliary space due to stack frames. The recursive style can help demonstrate understanding of recursion and problem decomposition, but it is less practical for very long strings compared to the iterative loop.
Both implementations depend on simple arithmetic operations and sequential traversal of a string. No sorting, hashing, or complex data structures are involved. The challenge mainly checks your understanding of ASCII values, absolute difference calculation, and careful iteration through adjacent elements.
Recommended for interviews: The iterative approach is the expected solution. Interviewers look for the ability to recognize that only adjacent characters matter and that a single pass through the string solves the problem in O(n) time with constant space. Implementing the recursive version can demonstrate deeper understanding, but the iterative method shows stronger practical judgment and efficiency.
This approach involves iterating through the string and calculating the absolute difference between each pair of adjacent characters, summing these differences to get the total score for the string.
We can easily access the ASCII value of a character in most programming languages by either using a built-in function or converting the character to an integer type.
This C program defines a function score_of_string that takes a string s as input. The function iterates over the string characters using indices, calculating the absolute difference between each character and the next. These differences are summed to obtain the total score.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as no extra space is used apart from a few variables.
This approach involves using recursion to calculate the score of the string. The function will compute the difference for the first two characters and then call itself recursively for the remaining substring.
This method is more of a demonstration of recursion as it is less optimal than the iterative method due to function call overhead.
This C solution uses a recursive function recursive_score, which calculates the score from an index. The base condition checks for the end of the string, and the recursive call processes the remaining substring.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the recursion stack.
We directly traverse the string s, calculating the sum of the absolute differences of the ASCII codes of adjacent characters.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative ASCII Difference Calculation | Time Complexity: O(n), where n is the length of the string. |
| Recursive ASCII Difference Calculation | Time Complexity: O(n), where n is the length of the string. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative ASCII Difference Calculation | O(n) | O(1) | Best general solution. Single pass with constant memory. |
| Recursive ASCII Difference Calculation | O(n) | O(n) | Useful for demonstrating recursion concepts or practicing recursive decomposition. |
Score of a String - Leetcode 3110 - Python • NeetCodeIO • 12,862 views views
Watch 9 more video solutions →Practice Score of a String with our built-in code editor and test cases.
Practice on FleetCode