LeetCode 2223: Sum of Scores of Built Strings

Explanation

To solve this problem, we can iterate through the string from left to right, keeping track of the longest common prefix between the current substring and the original string. We can maintain this information using a prefix array. The score of each substring is the length of the longest common prefix.

Algorithm

1. Initialize a variable n to store the length of the input string s.
2. Initialize a variable result to store the total sum of scores.
3. Initialize an array prefix of size n to store the prefix scores of each substring.
4. Iterate from index 1 to n in the input string s.
   • For each index i, calculate the longest common prefix between s.substring(0, i+1) and s itself.
   • Update prefix[i-1] with the length of the longest common prefix.
5. Calculate the total sum of scores by adding all elements of the prefix array.
6. Return the total sum of scores as the result.

Time Complexity

The time complexity of this algorithm is O(n) where n is the length of the input string s.

Space Complexity

The space complexity of this algorithm is O(n) for the prefix array.

class Solution {
    public int sumOfScores(String s) {
        int n = s.length();
        int result = 0;
        int[] prefix = new int[n];
        
        for (int i = 1; i <= n; i++) {
            prefix[i-1] = longestCommonPrefix(s.substring(0, i), s);
        }
        
        for (int p : prefix) {
            result += p;
        }
        
        return result;
    }
    
    private int longestCommonPrefix(String s1, String s2) {
        int i = 0;
        while (i < s1.length() && i < s2.length() && s1.charAt(i) == s2.charAt(i)) {
            i++;
        }
        return i;
    }
}