In this guide, you will get 2262. Total Appeal of A String LeetCode Solution with the best time and space complexity. The solution to Total Appeal of A String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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 <= 105
s consists of lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(26) = O(1)
2262. Total Appeal of A String LeetCode Solution in C++
class Solution {
public:
long long appealSum(string s) {
long ans = 0;
// the total appeal of all substrings ending in the index so far
int dp = 0;
vector<int> lastSeen(26, -1);
for (int i = 0; i < s.length(); ++i) {
// the total appeal of all substrings ending in s[i]
// = the total appeal of all substrings ending in s[i - 1]
// + the number of substrings ending in s[i] that contain only this s[i]
const int c = s[i] - 'a';
dp += i - lastSeen[c];
ans += dp;
lastSeen[c] = i;
}
return ans;
}
}; /* code provided by PROGIEZ */
2262. Total Appeal of A String LeetCode Solution in Java
class Solution {
public long appealSum(String s) {
long ans = 0;
// the total appeal of all substrings ending in the index so far
int dp = 0;
int[] lastSeen = new int[26];
Arrays.fill(lastSeen, -1);
for (int i = 0; i < s.length(); ++i) {
// the total appeal of all substrings ending in s[i]
// = the total appeal of all substrings ending in s[i - 1]
// + the number of substrings ending in s[i] that contain only this s[i]
final int c = s.charAt(i) - 'a';
dp += i - lastSeen[c];
ans += dp;
lastSeen[c] = i;
}
return ans;
}
} // code provided by PROGIEZ
2262. Total Appeal of A String LeetCode Solution in Python
class Solution:
def appealSum(self, s: str) -> int:
ans = 0
# the total appeal of all substrings ending in the index so far
dp = 0
lastSeen = {}
for i, c in enumerate(s):
# the total appeal of all substrings ending in s[i]
# = the total appeal of all substrings ending in s[i - 1]
# + the number of substrings ending in s[i] that contain only this s[i]
dp += i - lastSeen.get(c, -1)
ans += dp
lastSeen[c] = i
return ans # code by PROGIEZ
