Jobs

Interviews

Discussions

Score of a String

Easy

Asked by:

More companies

33 views

Topics:

StringsArrays

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.

Try coding it in LeetCode

Score of a String

Easy

Asked by:

33 views

Topics:

StringsArrays

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:

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`?
Is the input string `s` guaranteed to be a balanced parentheses string, or do I need to validate the input?
Can the input string `s` be empty or null? If so, what should I return?
Are there any limitations on the depth of nested parentheses? (e.g., very deeply nested strings that might cause stack overflow in recursive solutions)
Should I optimize for space complexity in addition to time complexity?

Brute Force Solution

Approach

To find the 'score' of a string using brute force, we essentially try out every single possible arrangement or combination within the string. We will evaluate each of these arrangements based on the rules of the problem to find the best one. This involves a lot of checking and comparing to find the optimal solution.

Here's how the algorithm would work step-by-step:

First, consider every possible way to divide the string into smaller pieces or substrings.
For each of these divisions, calculate its 'score' according to the problem's specific rules.
Keep track of the score for each division.
Compare all of the calculated scores to find the highest (or lowest, depending on the problem) score.
The division that results in the highest score is the answer.

Code Implementation

def score_of_a_string_brute_force(input_string):    number_of_characters = len(input_string)
    maximum_score = 0

    # Iterate through all possible substring starting positions
    for substring_start_index in range(number_of_characters + 1):

        # Iterate through all possible substring ending positions
        for substring_end_index in range(substring_start_index + 1, number_of_characters + 1):
            substring = input_string[substring_start_index:substring_end_index]
            current_score = calculate_substring_score(substring)

            # Keep track of the maximum score
            if current_score > maximum_score:
                maximum_score = current_score

    return maximum_score

def calculate_substring_score(substring):
    score = 0
    for character in substring:
        score += ord(character)
    return score

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach involves considering every possible division of the string into substrings. For a string of length n, there are 2^(n-1) possible ways to divide it (each position between characters can either be a split or not). For each division, we need to calculate the score, which may involve iterating through the substrings, but the dominant factor is the number of possible divisions. Therefore, the time complexity is driven by the exponential number of possible divisions, making it O(2^n).

Space Complexity

O(N) – The brute force approach described involves considering every possible division of the string into substrings. In the worst-case scenario, we might need to store all possible substrings, or the scores of all possible divisions, simultaneously. Since there can be O(N^2) substrings but typically a problem needs only keep track of the best seen score and temporary score lists, the algorithm will likely use an auxiliary array or list to store the division points themselves which can go up to N-1 and thus a space of N in the worst case. Therefore, the space complexity is O(N), where N is the length of the input string.

Optimal Solution

Approach

The best way to solve this problem is to keep track of the count of each letter. We then iterate through the string and keep track of the score.

Here's how the algorithm would work step-by-step:

First, we create a storage to count the occurrences of each letter in the string.
After the counts are gathered, we iterate through the string.
At each letter in the string, we multiply the value of the letter by the count of that letter.
Add up the results for each letter in the string to find the final score.

Code Implementation

def score_of_string(input_string):
    letter_counts = {}

    for letter in input_string:
        if letter in letter_counts:
            letter_counts[letter] += 1
        else:
            letter_counts[letter] = 1

    total_score = 0

    # Iterate through each character in the string
    for letter in input_string:
        # Lookup count of the current letter
        count_of_letter = letter_counts[letter]

        # Calculate the score and add to total
        total_score += (ord(letter) - ord('a') + 1) * count_of_letter

    # The score is calculated after iterating.
    return total_score

Big(O) Analysis

Time Complexity

O(n) – The first step iterates through the string of length n to count the occurrences of each letter. This is an O(n) operation. The second step iterates through the string again, which is another O(n) operation. Inside this loop, we perform a constant-time multiplication and addition for each character. Since we have two sequential loops that iterate through the string of length n once each, the total time complexity is O(n + n), which simplifies to O(n).

Space Complexity

O(1) – The provided solution utilizes a storage to count the occurrences of each letter in the string. Since we are dealing with letters of the alphabet and the alphabet size is fixed (typically 26 for English), the storage will have a maximum size independent of the input string length, N. Thus the space required for the letter counts remains constant. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string input	Return 0 as an empty string has a score of zero according to the problem's implied base case.
Null string input	Throw an IllegalArgumentException or return 0, depending on the specified error handling behavior.
String with single parentheses like '(' or ')'	Throw an IllegalArgumentException or return an error value since the input is not balanced.
String with unbalanced parentheses, e.g., '(()'	Throw an IllegalArgumentException or return an error value to indicate invalid input format.
String with maximum allowed length (consider constraints)	Ensure the solution's space and time complexity are within acceptable bounds and don't cause stack overflow or memory issues.
Deeply nested parentheses, e.g., '((((((())))))))'	Verify that the recursion depth doesn't exceed limits or that iterative solutions don't become excessively slow due to large stack usage.
String with many consecutive '()' pairs, e.g., '()()()()()'	Confirm that repeated addition doesn't cause performance bottlenecks and that the score is calculated correctly.
String with complex nesting and concatenation, e.g., '(()(()))'	Validate correct precedence and evaluation order of nested and concatenated expressions.

Empty string input

How to Handle:

Return 0 as an empty string has a score of zero according to the problem's implied base case.

Null string input

How to Handle:

Throw an IllegalArgumentException or return 0, depending on the specified error handling behavior.

String with single parentheses like '(' or ')'

How to Handle:

Throw an IllegalArgumentException or return an error value since the input is not balanced.

String with unbalanced parentheses, e.g., '(()'

How to Handle:

Throw an IllegalArgumentException or return an error value to indicate invalid input format.

String with maximum allowed length (consider constraints)

How to Handle:

Ensure the solution's space and time complexity are within acceptable bounds and don't cause stack overflow or memory issues.

Deeply nested parentheses, e.g., '((((((())))))))'

How to Handle:

Verify that the recursion depth doesn't exceed limits or that iterative solutions don't become excessively slow due to large stack usage.

String with many consecutive '()' pairs, e.g., '()()()()()'

How to Handle:

Confirm that repeated addition doesn't cause performance bottlenecks and that the score is calculated correctly.

String with complex nesting and concatenation, e.g., '(()(()))'

How to Handle:

Validate correct precedence and evaluation order of nested and concatenated expressions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`?
Is the input string `s` guaranteed to be a balanced parentheses string, or do I need to validate the input?
Can the input string `s` be empty or null? If so, what should I return?
Are there any limitations on the depth of nested parentheses? (e.g., very deeply nested strings that might cause stack overflow in recursive solutions)
Should I optimize for space complexity in addition to time complexity?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every possible way to divide the string into smaller pieces or substrings.
For each of these divisions, calculate its 'score' according to the problem's specific rules.
Keep track of the score for each division.
Compare all of the calculated scores to find the highest (or lowest, depending on the problem) score.
The division that results in the highest score is the answer.

Code Implementation

def score_of_a_string_brute_force(input_string):    number_of_characters = len(input_string)
    maximum_score = 0

    # Iterate through all possible substring starting positions
    for substring_start_index in range(number_of_characters + 1):

        # Iterate through all possible substring ending positions
        for substring_end_index in range(substring_start_index + 1, number_of_characters + 1):
            substring = input_string[substring_start_index:substring_end_index]
            current_score = calculate_substring_score(substring)

            # Keep track of the maximum score
            if current_score > maximum_score:
                maximum_score = current_score

    return maximum_score

def calculate_substring_score(substring):
    score = 0
    for character in substring:
        score += ord(character)
    return score

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The best way to solve this problem is to keep track of the count of each letter. We then iterate through the string and keep track of the score.

Here's how the algorithm would work step-by-step:

First, we create a storage to count the occurrences of each letter in the string.
After the counts are gathered, we iterate through the string.
At each letter in the string, we multiply the value of the letter by the count of that letter.
Add up the results for each letter in the string to find the final score.

Code Implementation

def score_of_string(input_string):
    letter_counts = {}

    for letter in input_string:
        if letter in letter_counts:
            letter_counts[letter] += 1
        else:
            letter_counts[letter] = 1

    total_score = 0

    # Iterate through each character in the string
    for letter in input_string:
        # Lookup count of the current letter
        count_of_letter = letter_counts[letter]

        # Calculate the score and add to total
        total_score += (ord(letter) - ord('a') + 1) * count_of_letter

    # The score is calculated after iterating.
    return total_score

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return 0 as an empty string has a score of zero according to the problem's implied base case.
Null string input	Throw an IllegalArgumentException or return 0, depending on the specified error handling behavior.
String with single parentheses like '(' or ')'	Throw an IllegalArgumentException or return an error value since the input is not balanced.
String with unbalanced parentheses, e.g., '(()'	Throw an IllegalArgumentException or return an error value to indicate invalid input format.
String with maximum allowed length (consider constraints)	Ensure the solution's space and time complexity are within acceptable bounds and don't cause stack overflow or memory issues.
Deeply nested parentheses, e.g., '((((((())))))))'	Verify that the recursion depth doesn't exceed limits or that iterative solutions don't become excessively slow due to large stack usage.
String with many consecutive '()' pairs, e.g., '()()()()()'	Confirm that repeated addition doesn't cause performance bottlenecks and that the score is calculated correctly.
String with complex nesting and concatenation, e.g., '(()(()))'	Validate correct precedence and evaluation order of nested and concatenated expressions.

Empty string input

How to Handle:

Return 0 as an empty string has a score of zero according to the problem's implied base case.

Null string input

How to Handle:

Throw an IllegalArgumentException or return 0, depending on the specified error handling behavior.

String with single parentheses like '(' or ')'

How to Handle:

Throw an IllegalArgumentException or return an error value since the input is not balanced.

String with unbalanced parentheses, e.g., '(()'

How to Handle:

Throw an IllegalArgumentException or return an error value to indicate invalid input format.

String with maximum allowed length (consider constraints)

How to Handle:

Ensure the solution's space and time complexity are within acceptable bounds and don't cause stack overflow or memory issues.

Deeply nested parentheses, e.g., '((((((())))))))'

How to Handle:

Verify that the recursion depth doesn't exceed limits or that iterative solutions don't become excessively slow due to large stack usage.

String with many consecutive '()' pairs, e.g., '()()()()()'

How to Handle:

Confirm that repeated addition doesn't cause performance bottlenecks and that the score is calculated correctly.

String with complex nesting and concatenation, e.g., '(()(()))'

How to Handle:

Validate correct precedence and evaluation order of nested and concatenated expressions.