Score of a String

Easy

#2763Time: 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.

Data structures

String

Prompt

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 <= 100
s consists 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 index reaches 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 index and the character at index + 1. It then adds this difference to the result of a recursive call to calculateScore with 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:
1. Define a recursive function, let's call it calculateScore(s, index).
2. Base Case: If the index reaches the last character (s.length() - 1), it means we've processed all pairs, so we return 0.
3. Recursive Step: The function calculates the absolute difference between the character at index and the character at index + 1. It then adds this difference to the result of a recursive call to calculateScore with the next index (index + 1).
4. The main function initiates the process by calling calculateScore(s, 0).
Code Snippet:

1class Solution {2    public int scoreOfString(String s) {3        return calculateScoreRecursive(s, 0);4    }5 6    private int calculateScoreRecursive(String s, int index) {7        // Base case: If we are at the last character, there are no more pairs to consider.8        if (index == s.length() - 1) {9            return 0;10        }11 12        // Calculate the score for the current adjacent pair.13        int currentDifference = Math.abs(s.charAt(index) - s.charAt(index + 1));14 15        // Recursively call for the next pair and add it to the current score.16        return currentDifference + calculateScoreRecursive(s, index + 1);17    }18}

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.

This is the most direct and optimal approach. We iterate through the string once, from the first character to the second-to-last. In each step, we calculate the absolute difference of ASCII values between the current character and the next one, and add this difference to a running total.

Algorithm

Initialize an integer variable score to 0.
Loop through the string from index i = 0 to s.length() - 2.
In each iteration, calculate the absolute difference between s.charAt(i) and s.charAt(i + 1).
Add the difference to the score.
Return the final score after the loop.

Walkthrough

The problem can be solved efficiently by iterating through the string and accumulating the score. We only need to look at each adjacent pair of characters once.

Algorithm:
1. Initialize an integer variable score to 0. This variable will accumulate the total score.
2. Loop through the string from the first character (index 0) up to the second-to-last character (index s.length() - 2). Let the loop variable be i.
3. Inside the loop, access the current character s.charAt(i) and the next character s.charAt(i + 1).
4. Calculate the absolute difference of their ASCII values using Math.abs(s.charAt(i) - s.charAt(i + 1)). In Java, char types can be implicitly converted to int for arithmetic operations.
5. Add this calculated difference to the score variable.
6. After the loop completes, the score variable holds the final result. Return score.
Code Snippet:

1class Solution {2    public int scoreOfString(String s) {3        int score = 0;4        for (int i = 0; i < s.length() - 1; i++) {5            // Get the ASCII values of adjacent characters and add their absolute difference to the score.6            score += Math.abs(s.charAt(i) - s.charAt(i + 1));7        }8        return score;9    }10}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string's characters once in a single loop that runs N-1 times.

Space

O(1). We only use a constant amount of extra space for variables like `score` and the loop counter `i`, regardless of the input string's size.

Trade-offs

Pros

Optimal time complexity as we must examine each character pair once.
Optimal space complexity, using only a few variables.
Very simple, readable, and easy to implement.

Cons

There are no significant disadvantages to this approach as it is the most efficient solution for this problem.

Solutions

Solution

1public class Solution {2    public int ScoreOfString(string s) {3        int ans = 0;4        for (int i = 1; i < s.Length; ++i) {5            ans += Math.Abs(s[i] - s[i - 1]);6        }7        return ans;8    }9}

1class Solution {2public3  int scoreOfString(String s) {4    int ans = 0;5    for (int i = 1; i < s.length(); ++i) {6      ans += Math.abs(s.charAt(i - 1) - s.charAt(i));7    }8    return ans;9  }10}

1class Solution {2public:3  int scoreOfString(string s) {4    int ans = 0;5    for (int i = 1; i < s.size(); ++i) {6      ans += abs(s[i] - s[i - 1]);7    }8    return ans;9  }10};

1class Solution:2    def scoreOfString(self, s: str) -> int: return sum(abs(a - b)3                                                       for a, b in pairwise(map(ord, s)))

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.

← Previous

Previous problem

Next problem