Kattis Summertrip

Description: A classic preprocessing problem.
Publish Date: Calculating Date
Tags: [[competitive programming], [dynamic programming], [cpp]]

The original question description can be found here. This problem bugged me for a while since I was pretty new to this type of preprocessing problems. The gist is that given a string, find all possible substrings with its head and last unique in the substring.

The naive solution is to find all substrings and valide them one by one, but the string can be as long as $10^6$ , and finding all substrings is of $O(n^2)$ complexity, rendering it infeasible to do so. A different way to think of finding this is to keep a record $DP[A][B]$ where A and B are characters. $DP[A][B]$ is whether or not we have seen B when we read a character A in the string. This works because we assume both of them must be unique to qualify as a valid substring. We build $DP$ from start to end, with each iteration covering future uniqueness assessments. However, this solution does not produce correct substrings. It merely counts them. Take string $aaaaaaab$ as an example, the $ucount[b]$ is actually produced by the first $a$ , but the actual valid substring is $ab$ .

#include <bits/stdc++.h>
using namespace std;
int ucount[26] =
    {}; // when ending with character C, the total unique combination currently is ucount[C].
unsigned long long had_prev[26][26] =
    {}; // had_prev[A][B] = When encountering character A, we have seen B (aka B is BEFORE A)
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    string s;
    getline(cin, s);
 
    size_t len = s.size();
    unsigned long long good_trip = 0;
    for (size_t i = 0; i < len; i++)
    {
        size_t ch = s[i] - 'a';
        good_trip += ucount[ch];
        ucount[ch] = 0; // reset unique combination (we've registered)
        memset(had_prev[ch], 0,
               sizeof(had_prev[ch])); // reset everything for ch being the start (because we
                                      // just saw A. jettisoned ucount)
        for (size_t j = 0; j < 26; j++)
        {
            if (j == ch)
            {
                continue;
            }
            if (!had_prev[j][ch]) // haven't seen ch yet (unique)
            {
                had_prev[j][ch] = 1;
                ucount[j]++; // should we encounter j in the future, we will get the unique combo
                // uncertainty = cache
            }
        }
    }
 
    cout << good_trip << '\n';
 
    return 0;
}