828. Count Unique Characters of All Substrings of a Given String

Approach 1: DP

• Time: $O(n)$
• Space: $O(26) = O(1)$

C++JavaPython

class Solution {
 public:
  int uniqueLetterString(string s) {
    int ans = 0;
    // the number of unique letters in all the substrings ending in the index so
    // far
    int dp = 0;
    vector<int> lastCount(26);
    vector<int> lastSeen(26, -1);

    for (int i = 0; i < s.length(); ++i) {
      const int c = s[i] - 'A';
      const int newCount = i - lastSeen[c];
      // Substract the duplicates.
      dp -= lastCount[c];
      // Add count of s[lastSeen[c] + 1..i], s[lastSeen[c] + 2..i], ..., s[i].
      dp += newCount;
      lastCount[c] = newCount;
      lastSeen[c] = i;
      ans += dp;
    }

    return ans;
  }
};

class Solution {
  public int uniqueLetterString(String s) {
    int ans = 0;
    // the number of unique letters in all the substrings ending in the index so
    // far
    int dp = 0;
    int[] lastCount = new int[26];
    int[] lastSeen = new int[26];
    Arrays.fill(lastSeen, -1);

    for (int i = 0; i < s.length(); ++i) {
      final int c = s.charAt(i) - 'A';
      final int newCount = i - lastSeen[c];
      // Substract the duplicates.
      dp -= lastCount[c];
      // Add count of s[lastSeen[c] + 1..i], s[lastSeen[c] + 2..i], ..., s[i].
      dp += newCount;
      lastCount[c] = newCount;
      lastSeen[c] = i;
      ans += dp;
    }

    return ans;
  }
}

class Solution:
  def uniqueLetterString(self, s: str) -> int:
    ans = 0
    # the number of unique letters in all the substrings ending in the index so
    # far
    dp = 0
    lastCount = {}
    lastSeen = {}

    for i, c in enumerate(s):
      newCount = i - lastSeen.get(c, -1)
      # Substract the duplicates.
      dp -= lastCount.get(c, 0)
      # Add count of s[lastSeen[c] + 1..i], s[lastSeen[c] + 2..i], ..., s[i].
      dp += newCount
      lastCount[c] = newCount
      lastSeen[c] = i
      ans += dp

    return ans

Approach 2: Combinatorics

• Time: $O(n)$
• Space: $O(26) = O(1)$

C++JavaPython

class Solution {
 public:
  int uniqueLetterString(string s) {
    const int n = s.length();
    int ans = 0;
    // lastSeen[c] := the index of the last time ('a' + i) appeared
    vector<int> lastSeen(26, -1);
    // prevSeen[c] := the previous index of the last time ('a' + i) appeared
    vector<int> prevLastSeen(26, -1);

    for (int i = 0; i < n; ++i) {
      const int c = s[i] - 'A';
      if (lastSeen[c] != -1)
        ans += (i - lastSeen[c]) * (lastSeen[c] - prevLastSeen[c]);
      prevLastSeen[c] = lastSeen[c];
      lastSeen[c] = i;
    }

    for (int c = 0; c < 26; ++c)
      ans += (n - lastSeen[c]) * (lastSeen[c] - prevLastSeen[c]);

    return ans;
  }
};

class Solution {
  public int uniqueLetterString(String s) {
    int n = s.length();
    int ans = 0;
    // lastSeen[c] := the index of the last time ('a' + i) appeared
    int[] lastSeen = new int[26];
    // prevSeen[c] := the previous index of the last time ('a' + i) appeared
    int[] prevLastSeen = new int[26];
    Arrays.fill(lastSeen, -1);
    Arrays.fill(prevLastSeen, -1);

    for (int i = 0; i < n; ++i) {
      final int c = s.charAt(i) - 'A';
      if (lastSeen[c] != -1)
        ans += (i - lastSeen[c]) * (lastSeen[c] - prevLastSeen[c]);
      prevLastSeen[c] = lastSeen[c];
      lastSeen[c] = i;
    }

    for (int c = 0; c < 26; ++c)
      ans += (n - lastSeen[c]) * (lastSeen[c] - prevLastSeen[c]);

    return ans;
  }
}

class Solution:
  def uniqueLetterString(self, s: str) -> int:
    ans = 0
    # lastSeen[c] := the index of the last time ('a' + i) appeared
    lastSeen = collections.defaultdict(lambda: -1)
    # prevSeen[c] := the previous index of the last time ('a' + i) appeared
    prevLastSeen = collections.defaultdict(lambda: -1)

    for i, c in enumerate(s):
      if c in lastSeen:
        ans += (i - lastSeen[c]) * (lastSeen[c] - prevLastSeen[c])
      prevLastSeen[c] = lastSeen[c]
      lastSeen[c] = i

    for c in string.ascii_uppercase:
      ans += (len(s) - lastSeen[c]) * (lastSeen[c] - prevLastSeen[c])

    return ans