Total Appeal of A String | Leetcode - 2262 | Dynamic Programming | Hash Table

The appeal of a string is the number of distinct characters found in the string.

• For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.

Given a string s, return the total appeal of all of its substrings.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abbca"
Output: 28
Explanation: The following are the substrings of "abbca":
- Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.

Example 2:

Input: s = "code"
Output: 20
Explanation: The following are the substrings of "code":
- Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4: "code" has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.

Constraints:

• 1 <= s.length <= 10<sup>5</sup>

• s consists of lowercase English letters.

Solution:

class Solution {
/*
    Appraoch - 2 - Optimised
    Think what we want, and then proceed to check how to solve
    Here, we need to calculate the length of the unique elements in all substrings

    How do we identify the maximum non-consecutive elements?
    - Iterate througn the string, for each iteration, find the distance between 'i' and previous positon of current character(s[i]) => "distance"

    How do we get all the substrings ending at current position 'i', i.e., end should be at 'i'?
    - Keep adding up the "distance" in "currResult"

    How do we get all the substrings till the current position 'i'?
    - Keep adding the "currResult" to "result"
*/
    public long appealSum(String s) {
        long result = 0l;
        long currResult = 0l; // this stores the appeal of all substrings till current position 
        int[] prev = new int[26];

        for(int i=0; i<s.length(); i++) {
            // calculate the distance between current positon and previous position of the current character 
            currResult += (i+1 - prev[s.charAt(i) -'a']);
            prev[s.charAt(i) - 'a'] = i+1;
            result += currResult;
        }

        return result;
    }

    // Aoproach - 1 - Finding unique characters in all substrings
    private int findUnique(String s, int start, int end) {
        HashSet<Character> set = new HashSet<>();
        for(int i= start; i<=end; i++) {
            set.add(s.charAt(i));
        }
        return set.size();
    }

    public long appealSum_UsingIteration(String s) {
        long result = 0L;
        // To get all substrings
        for(int i=0; i<s.length(); i++) {
            for(int j=s.length()-1; j>=i; j--){
                result += (long)findUnique(s, i, j);
            }
        }
        return result;
    }
}