LeetCode 2223: Sum of Scores of Built Strings Solution

Master LeetCode problem 2223 (Sum of Scores of Built Strings), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2223. Sum of Scores of Built Strings

Hard

String Binary Search Rolling Hash Suffix Array String Matching Hash Function

Problem Explanation

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

Initialize a variable n to store the length of the input string s.
Initialize a variable result to store the total sum of scores.
Initialize an array prefix of size n to store the prefix scores of each substring.
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.
Calculate the total sum of scores by adding all elements of the prefix array.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2223 (Sum of Scores of Built Strings)?

This page provides optimized solutions for LeetCode problem 2223 (Sum of Scores of Built Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2223 (Sum of Scores of Built Strings)?

The time complexity for LeetCode 2223 (Sum of Scores of Built Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2223 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2223 in Java, C++, or Python.

Back to LeetCode Solutions