Score of a String
EasyPrompt
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 <= 100sconsists only of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses recursion to solve the problem. A helper function is defined that processes the string one character pair at a time. The score for the current pair is calculated and added to the result of the recursive call for the rest of the string.
Algorithm
- Define a recursive function, let's call it
calculateScore(s, index). - Base Case: If the
indexreaches the second-to-last position (s.length() - 1), it means we've processed all pairs, so we return 0. - Recursive Step: The function calculates the absolute difference between the character at
indexand the character atindex + 1. It then adds this difference to the result of a recursive call tocalculateScorewith the next index (index + 1). - The main function initiates the process by calling
calculateScore(s, 0).
Walkthrough
The core idea is to break the problem down into smaller, self-similar subproblems. We can define a function that calculates the score for a substring starting at a given index.
-
Algorithm:
- Define a recursive function, let's call it
calculateScore(s, index). - Base Case: If the
indexreaches the last character (s.length() - 1), it means we've processed all pairs, so we return 0. - Recursive Step: The function calculates the absolute difference between the character at
indexand the character atindex + 1. It then adds this difference to the result of a recursive call tocalculateScorewith the next index (index + 1). - The main function initiates the process by calling
calculateScore(s, 0).
- Define a recursive function, let's call it
-
Code Snippet:
class Solution { public int scoreOfString(String s) { return calculateScoreRecursive(s, 0); } private int calculateScoreRecursive(String s, int index) { // Base case: If we are at the last character, there are no more pairs to consider. if (index == s.length() - 1) { return 0; } // Calculate the score for the current adjacent pair. int currentDifference = Math.abs(s.charAt(index) - s.charAt(index + 1)); // Recursively call for the next pair and add it to the current score. return currentDifference + calculateScoreRecursive(s, index + 1); }}Complexity
Time
O(N), where N is the length of the string `s`. The recursive function is called N-1 times, and each call performs a constant number of operations.
Space
O(N) in the worst case. This is due to the recursion depth, as each function call adds a new frame to the call stack. The maximum depth of the recursion is N.
Trade-offs
Pros
Provides a functional, declarative way to express the solution.
Can be a good way to break down problems into smaller subproblems.
Cons
Less efficient in terms of space compared to an iterative solution due to the call stack overhead.
For very long strings (not an issue with the given constraints), it could lead to a
StackOverflowError.Can be less intuitive than a simple loop for this particular problem.
Solutions
Solution
public class Solution { public int ScoreOfString(string s) { int ans = 0; for (int i = 1; i < s.Length; ++i) { ans += Math.Abs(s[i] - s[i - 1]); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.