LeetCode 828: Count Unique Characters of All Substrings of a Given String Solution

Master LeetCode problem 828 (Count Unique Characters of All Substrings of a Given String), 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.

828. Count Unique Characters of All Substrings of a Given String

Hard

Hash Table String Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we need to count the number of unique characters in all substrings of a given string. We can achieve this by iterating through all possible substrings and counting the unique characters in each substring.

Here is the algorithmic idea:

Initialize a variable result to store the final sum of unique characters.
Iterate through all possible substrings of the given string.
For each substring, calculate the number of unique characters using a HashSet to store the characters.
Add the count of unique characters in each substring to the result.
Return the result as the final answer.

Time Complexity: O(n^2) where n is the length of the input string. Space Complexity: O(n) for the HashSet.

Solution Code

class Solution {
    public int uniqueLetterString(String s) {
        int mod = 1000000007;
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int left = i, right = i;
            while (left >= 0 && s.charAt(left) != s.charAt(i)) {
                left--;
            }
            while (right < s.length() && s.charAt(right) != s.charAt(i)) {
                right++;
            }
            result = (result + (i - left) * (right - i)) % mod;
        }
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 828 (Count Unique Characters of All Substrings of a Given String)?

This page provides optimized solutions for LeetCode problem 828 (Count Unique Characters of All Substrings of a Given String) 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 828 (Count Unique Characters of All Substrings of a Given String)?

The time complexity for LeetCode 828 (Count Unique Characters of All Substrings of a Given String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 828 on DevExCode?

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

Back to LeetCode Solutions