Problem
Let's define a function countUniqueChars(s)
that returns the number of unique characters on s
.
- For example, calling
countUniqueChars(s)
ifs = "LEETCODE"
then"L"
,"T"
,"C"
,"O"
,"D"
are the unique characters since they appear only once ins
, thereforecountUniqueChars(s) = 5
.
Given a string s
, return the sum of countUniqueChars(t)
where t
is a substring of s
. The test cases are generated such that the answer fits in a 32-bit integer.
Notice that some substrings can be repeated so in this case you have to count the repeated ones too.
Example 1:
Input: s = "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Example 2:
Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.
Example 3:
Input: s = "LEETCODE"
Output: 92
Constraints:
1 <= s.length <= 10^5
s
consists of uppercase English letters only.
Solution
class Solution {
public int uniqueLetterString(String s) {
// Store last index of a character.
int[] lastCharIdx = new int[26];
// Store last to last index of a character.
// Eg. For ABA - lastCharIdx = 2, prevLastCharIdx = 0.
int[] prevLastCharIdx = new int[26];
Arrays.fill(lastCharIdx, -1);
Arrays.fill(prevLastCharIdx, -1);
int len = s.length();
int[] dp = new int[len];
int accumCount = 1;
dp[0] = 1;
lastCharIdx[s.charAt(0) - 'A'] = 0;
prevLastCharIdx[s.charAt(0) - 'A'] = 0;
for (int i = 1; i < len; i++) {
char ch = s.charAt(i);
int chIdx = ch - 'A';
int lastSeenIdx = lastCharIdx[chIdx];
int prevLastIdx = prevLastCharIdx[chIdx];
dp[i] = dp[i - 1] + 1;
if (lastSeenIdx == -1) {
dp[i] += i;
} else {
// Add count for curr index from index of last char appearance.
dp[i] += (i - lastSeenIdx - 1);
if (prevLastIdx == lastSeenIdx) {
// if last char idx is the only appearance of the char from left so far,
// substrings that overlap [0, lastSeenIdx] will need count to be discounted, as
// current char will cause duplication.
dp[i] -= lastSeenIdx + 1;
} else {
dp[i] -= (lastSeenIdx - prevLastIdx);
}
}
prevLastCharIdx[chIdx] = lastSeenIdx;
lastCharIdx[chIdx] = i;
accumCount += dp[i];
}
return accumCount;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).