LeetCode 2262: Total Appeal of A String

Explanation

To solve this problem, we can iterate through all substrings of the input string s and calculate the appeal of each substring. We can do this by maintaining a frequency array to count the occurrences of each character within the current substring. Then, we iterate over all possible substrings of different lengths and calculate the total appeal.

• Initialize a variable totalAppeal to store the sum of appeals of all substrings.
• Iterate over all possible starting positions i from 0 to n-1 where n is the length of the input string.
• For each starting position i, iterate over all possible ending positions j from i to n-1.
• For each substring from position i to j, maintain a frequency array to count the occurrences of each character.
• Calculate the appeal of the current substring as the number of unique characters in the frequency array.
• Update the totalAppeal by adding the appeal of the current substring.
• Finally, return the totalAppeal.

The time complexity of this approach is O(n^2) where n is the length of the input string s. The space complexity is O(26) for the frequency array, which is constant.

class Solution {
    public int totalAppeal(String s) {
        int totalAppeal = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                int appeal = 0;
                for (int k = 0; k < 26; k++) {
                    if (freq[k] > 0) {
                        appeal++;
                    }
                }
                totalAppeal += appeal;
            }
        }

        return totalAppeal;
    }
}