Algorithm (Dynamic Programming)

1. Let $f(i)$ the sum of unique characters for all substrings that ends with $S[i],$ namely $$f(i)=\sum_{c,c\text{ ends with }S[i]}\text{UNIQUE}(c).$$
2. Then we have $$f(i)=\begin{cases} f(i-1)+i+1 & \text{if }\mathcal{O}_{1}(i)=\emptyset\text{ and }\mathcal{O}_{2}(i)=\emptyset\\\\ f(i-1)+i-\mathcal{O}_{1}(i)-(\mathcal{O}_{1}(i)+1) & \text{if }\mathcal{O}_{1}(i)\neq\emptyset\text{ and }\mathcal{O}_{2}(i)=\emptyset\\\\ f(i-1)+(i-\mathcal{O}_{1}(i))-(\mathcal{O}_{1}(i)-\mathcal{O}_{2}(i)) & \text{if }\mathcal{O}_{1}(i)\neq\emptyset\text{ and }\mathcal{O}_{2}(i)\neq\emptyset \end{cases},$$ where $\mathcal{O}_{k}(i)$ is the $k$-th occurence in term of index of $S[i]$ when scanning from $S[i]$ towards left.

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };


class Solution {
 public:
  int uniqueLetterString(string S) {
    const struct {
      mutable optional<int> f[10000] = {};
    } memo;

    auto find_backward = [&](int pos) {
      auto fst = optional<int>{};
      auto snd = optional<int>{};
      for (int i = pos - 1; i >= 0 and (not fst or not snd); --i) {
        if (S[i] == S[pos] and not fst.has_value())
          fst = i;
        else if (S[i] == S[pos] and fst.has_value())
          snd = i;
      }
      return array<optional<int>, 2> {fst, snd};
    };

    auto f = rec([&, memo = std::ref(memo.f)](auto &&f, int i) -> int {
      if (memo[i])
        return *memo[i];
      else
        return *(memo[i] = [&] {
          if (i == 0)
            return 1;
          else {
            const auto [fst, snd] = find_backward(i);
            if (not fst and not snd)
              return f(i - 1) + i + 1;
            else if (fst and not snd)
              return f(i - 1) + (i - fst.value()) - (fst.value() + 1);
            else if (fst and snd)
              return f(i - 1) + (i - fst.value()) - (fst.value() - snd.value());
            else
              throw std::domain_error("");
          }
        }());
    });

    const auto solution = [&](int acc = 0) {
      for (int i = 0; i < size(S); ++i) 
        acc += f(i);
      return acc;
    }();

    return solution ;
  }
};