unique_chars_of_all_substrings.cc

// https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string

/*
 * # Brute force approach
 *
 * Generate all substrings, and count the unique chars in each.
 *
 * Time complexity: O(n^2) to generate all substrings, O(n) to count unique chars for
 * each. Total: O(n^3).
 *
 * Space complexity: O(n). We reuse the same space to store all substrings.
 *
 * # Dynamic Programming Intuition
 *
 * Every char in the string eventually "contributes" to the answer.
 *
 * Let s be the input string, with s[i] denoting the i-th char in s.
 *
 * Let left[i] be the number of chars between s[i] and the previous occurrence of s[i].
 *
 * Let right[i] be the number of chars between s[i] and the next occurrence of s[i].
 *
 * Then, the contribution of s[i] is c[i] = left[i] * right[i], and the answer is:
 *
 * \sum_{i = 1}^{n} c[i]
 */

class Solution {
public:
    // O(n) time and O(n) space, easier to understand
    int uniqueLetterString0(string& s) {
        int n = s.length(), i, j;

        vector<int> L(n, -1), R(n, -1);
        vector<int> lastL(26, -1), lastR(26, n);

        for (i = 0; i < n; i++){
            L[i] = i - lastL[s[i] - 'A'];
            lastL[s[i] - 'A'] = i;

            j = n - 1 - i; // opposite direction
            R[j] = lastR[s[j] - 'A'] - j;
            lastR[s[j] - 'A'] = j;
        }

        int ans = 0;

        for (i = 0; i < n; i++) ans += L[i] * R[i];

        return ans;
    }

    // O(n) time and constant space
    int uniqueLetterString(string& s) {
        int offsets[26][2], sum = 0, n = s.length(), i, index;
        memset(offsets, -1, sizeof(int) * 52);

        for (i = 0; i < n; i++) {
            index = s[i] - 'A';

            // count lefmost contributions
            sum += (offsets[index][1] - offsets[index][0]) * (i - offsets[index][1]);

            // update last 2 occurrences of s[i]
            offsets[index][0] = offsets[index][1];
            offsets[index][1] = i;
        }

        for (i = 0; i < 26; i++) // count rightmost contributions
            sum += (offsets[i][1] - offsets[i][0]) * (n - offsets[i][1]);

        return sum;
    }
};