Leetcode: 2262. Total Appeal of A String

Problem Statement

• Is there an alternative problem easier to solve? Count the number of substring that \(s[i]\) is the first appearance of \(s[i]\) on it. For strings starting on \(i\), it will appear on \(N - i\) of those. It will appear in the mid of \((i - prev[s[i]]) \times (N - i - 1)\) where \(prev[s[i]]\) is the last occurrence of \(s[i]\) on \(0..(i-1)\). Time complexity is \(O(n)\) and space is \(O(1)\).

class Solution:
    def appealSum(self, s: str) -> int:
        N = len(s)
        last = defaultdict(lambda: -1)
        prev = [-1] * N
        for i in range(N):
            prev[i] = last[s[i]]
            last[s[i]] = i
        ans = 0
        for i in range(N):
            ans += (N - i) * (i - prev[i])
        return ans