Sum of Scores of Built Strings

Hard

Asked by:

11 views

Topics:

Strings

You are building a string s of length n one character at a time, prepending each new character to the front of the string. The strings are labeled from 1 to n, where the string with length i is labeled s_i.

For example, for s = "abaca", s₁ == "a", s₂ == "ca", s₃ == "aca", etc.

The score of s_i is the length of the longest common prefix between s_i and s_n (Note that s == s_n).

Given the final string s, return the sum of the score of every s_i.

Example 1:

Input: s = "babab"
Output: 9
Explanation:
For s₁ == "b", the longest common prefix is "b" which has a score of 1.
For s₂ == "ab", there is no common prefix so the score is 0.
For s₃ == "bab", the longest common prefix is "bab" which has a score of 3.
For s₄ == "abab", there is no common prefix so the score is 0.
For s₅ == "babab", the longest common prefix is "babab" which has a score of 5.
The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.

Example 2:

Input: s = "azbazbzaz"
Output: 14
Explanation: 
For s₂ == "az", the longest common prefix is "az" which has a score of 2.
For s₆ == "azbzaz", the longest common prefix is "azb" which has a score of 3.
For s₉ == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9.
For all other s_i, the score is 0.
The sum of the scores is 2 + 3 + 9 = 14, so we return 14.

Constraints:

1 <= s.length <= 10⁵
s consists 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:

Can you clarify the constraints on the string length? Is there a maximum length I should be aware of?
Can the input string be empty or null? If so, what should the function return in those cases?
By 'score' are we referring to the length of the longest common prefix between the built string and the suffixes of the original string?
Are we concerned about integer overflow when calculating the sum of scores? If so, what should I do to handle it?
Can you provide an example to illustrate how the 'score' is calculated for a built string?

Brute Force Solution

Approach

The problem asks to create strings from a given string and find the sum of scores of each of these created strings. The brute force method involves exhaustively generating every possible string that can be built and then calculate the score for each of those created strings. Finally the sum of all scores is returned.

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

Start by considering every possible substring that begins at the start of the original string.
Check if the substring exists later in the original string.
If it exists, calculate its score (which is the length of the substring).
Add the score to a running total.
Repeat this process, but this time consider every substring that begins at the second position in the original string.
Continue doing this for every possible starting position in the original string.
The final running total represents the sum of scores for all the substrings we found.

Code Implementation

def sum_scores_of_built_strings_brute_force(input_string):
    total_score = 0

    for start_index in range(len(input_string)): 
        for substring_length in range(1, len(input_string) - start_index + 1):
            substring = input_string[start_index:start_index + substring_length]

            # Iterate through the rest of the string
            for search_index in range(start_index + 1, len(input_string) - substring_length + 1):

                # Check if substring exists later in the input
                if input_string[search_index:search_index + substring_length] == substring:
                    total_score += substring_length

    return total_score

Big(O) Analysis

Time Complexity

O(n^3) – The outer loop iterates 'n' times, where n is the length of the original string, considering each possible starting position for a substring. Inside this loop, we generate substrings, which takes O(n) time in the worst case for each starting position. For each substring, we need to check if it exists later in the original string, which, in the worst case, requires another O(n) operation using string search or comparison methods. Therefore, the total time complexity becomes O(n * n * n), which simplifies to O(n^3).

Space Complexity

O(1) – The described algorithm primarily uses a running total to accumulate scores and iterates through substrings using index variables. No auxiliary data structures like arrays, hash maps, or trees are created to store intermediate results or substrings. Therefore, the space required remains constant, irrespective of the input string's length (N), making the auxiliary space complexity O(1).

Optimal Solution

Approach

The trick is to efficiently compare parts of the string to themselves to find repeating patterns. By recognizing these patterns, we can avoid redundant calculations and determine the score much faster than checking every possible combination. It's like finding hidden shortcuts within the string itself.

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

First, consider the entire string. See how much of the beginning of the string matches the end of the string.
The length of that matching part gives us an initial score.
Next, consider a shorter string, removing the very first character from the beginning.
Again, see how much the start of this shorter string matches the end.
Add this new match length to the score.
Repeat this process, each time removing the first character, creating even shorter strings.
Keep adding the length of the longest matching start and end parts of these strings to the overall score.
Continue until there is almost no string left to consider.
The final score is the sum of all these matching lengths.

Code Implementation

def sum_of_scores_of_built_strings(input_string):
    string_length = len(input_string)
    total_score = 0

    for i in range(string_length):
        substring = input_string[i:]
        substring_length = len(substring)
        match_length = 0

        # We compare prefixes and suffixes
        for j in range(substring_length):
            if substring[:j+1] == substring[substring_length-j-1:]:
                match_length = j + 1

        # Update total score with length of match found
        total_score += match_length

    return total_score

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through substrings of decreasing lengths, where the initial string has length n. For each substring, a comparison is made between the prefix and suffix to determine the matching length. In the worst-case scenario, the comparison of the prefix and suffix within each substring takes O(n) time. Since we iterate through n substrings, each potentially requiring O(n) comparisons, the overall time complexity becomes approximately n * n operations. This can be simplified to O(n²).

Space Complexity

O(1) – The described algorithm iteratively compares substrings without creating any auxiliary data structures that scale with the input string's length. It only uses a few constant space variables to track the matching lengths and loop indices. Therefore, the space complexity remains constant irrespective of the input string's size, N. The algorithm's auxiliary space usage does not depend on N.

Edge Cases

Case	How to Handle
Null or empty string as input	Return 0 since there's nothing to build from and nothing to score.
String with a single character	The suffix is the single character and the length is the score.
String with all identical characters (e.g., 'aaaa')	Suffixes are all the same character repeated decreasingly and the scores are easily determined.
Very long input string causing potential integer overflow	Use a 64-bit integer to store the sum of scores to avoid potential overflow.
Input string with special characters or unicode characters	Ensure the algorithm handles these characters correctly during string comparison.
String containing a very long repeating pattern	The algorithm should still work correctly, but consider the computational complexity impact.
Maximum string length approaching memory limits	The KMP algorithm optimizes substring matching; confirm suffix storage doesn't exhaust memory.
String where the longest common prefix with suffixes is always very short	The algorithm should handle this gracefully; performance would not be optimal, but correctness is maintained.

Null or empty string as input

How to Handle:

Return 0 since there's nothing to build from and nothing to score.

String with a single character

How to Handle:

The suffix is the single character and the length is the score.

String with all identical characters (e.g., 'aaaa')

How to Handle:

Suffixes are all the same character repeated decreasingly and the scores are easily determined.

Very long input string causing potential integer overflow

How to Handle:

Use a 64-bit integer to store the sum of scores to avoid potential overflow.

Input string with special characters or unicode characters

How to Handle:

Ensure the algorithm handles these characters correctly during string comparison.

String containing a very long repeating pattern

How to Handle:

The algorithm should still work correctly, but consider the computational complexity impact.

Maximum string length approaching memory limits

How to Handle:

The KMP algorithm optimizes substring matching; confirm suffix storage doesn't exhaust memory.

String where the longest common prefix with suffixes is always very short

How to Handle:

The algorithm should handle this gracefully; performance would not be optimal, but correctness is maintained.