Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/828.html
828. Unique Letter String (Hard)
A character is unique in string S if it occurs exactly once in it.
For example, in string S = "LETTER", the only unique characters are "L" and "R".
Let's define UNIQ(S) as the number of unique characters in string S.
For example, UNIQ("LETTER") = 2.
Given a string S with only uppercases, calculate the sum of UNIQ(substring) over all non-empty substrings of S.
If there are two or more equal substrings at different positions in S, we consider them different.
Since the answer can be very large, return the answer modulo 10 ^ 9 + 7.
Example 1:
Input: "ABC" Output: 10 Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC". Evey substring is composed with only unique letters. Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Example 2:
Input: "ABA"
Output: 8
Explanation: The same as example 1, except uni("ABA") = 1.
Note: 0 <= S.length <= 10000.
Companies:
ForUsAll
Related Topics:
Two Pointers
Solution 1. Brute Force
Keep track of counts of letters. When the count reachs 1, increment unique count. When the count reachs 2, decrement unique count.
// OJ: https://leetcode.com/problems/unique-letter-string
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
int uniqueLetterString(string S) {
int mod = 1e9 + 7, N = S.size(), ans = 0;
for (int i = 0; i < N; ++i) {
int cnts[26] = {0}, prev = 0, two = 0;
for (int j = i; j < N && two != 26; ++j) {
cnts[S[j] - 'A']++;
int cur = prev;
if (cnts[S[j] - 'A'] == 1) ++cur;
else if (cnts[S[j] - 'A'] == 2) {
--cur;
two++;
}
ans = (ans + cur) % mod;
prev = cur;
}
}
return ans;
}
};
Solution 2. Split by Letter
Look at each letter one by one. Consider a sequence A B A CD A, assume the indexes of A are [0,2,5]. For the middle A, how many times does it show up in the substrings?
BA
BAC
BACD
A
AC
ACD
6 times. Because the start position can be 1 or 2 (from B or from middle A), and the end position can be 3, 4, or 5 (ends before C, D, or A). They are simply the difference between the indexes of As. 6 = (2 - 0) * (5 - 2) = 2 * 3.
So in general, keep track of positions of letters. (pos[i - 1] - pos[i]) * (pos[i + 1] - pos[i]) is the unique count of letter S[i] in all substrings.
// OJ: https://leetcode.com/problems/unique-letter-string/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int uniqueLetterString(string S) {
unordered_map<char, vector<int>> m;
for (int i = 0; i < S.size(); ++i) {
m[S[i]].push_back(i);
}
int ans = 0, mod = 1e9 + 7;
for (auto it = m.begin(); it != m.end(); ++it) {
char c = it->first;
auto &v = it->second;
for (int i = 0; i < v.size(); ++i) {
int prev = i == 0 ? -1 : v[i - 1];
int next = i < v.size() - 1 ? v[i + 1] : S.size();
ans = (ans + (v[i] - prev) * (next - v[i]) % mod) % mod;
}
}
return ans;
}
};
-
class Solution { public int uniqueLetterString(String s) { final int MODULO = 1000000007; Map<Character, List<Integer>> map = new HashMap<Character, List<Integer>>(); int length = s.length(); for (int i = 0; i < length; i++) { char c = s.charAt(i); List<Integer> indices = map.getOrDefault(c, new ArrayList<Integer>()); indices.add(i); map.put(c, indices); } int count = 0; Set<Character> keySet = map.keySet(); for (char c : keySet) { List<Integer> indices = map.get(c); int size = indices.size(); for (int i = 0; i < size; i++) { int currIndex = indices.get(i); int prevIndex = i > 0 ? indices.get(i - 1) : -1; int nextIndex = i < size - 1 ? indices.get(i + 1) : length; count = (count + (currIndex - prevIndex) * (nextIndex - currIndex)) % MODULO; } } return count; } } ############ class Solution { public int uniqueLetterString(String s) { List<Integer>[] d = new List[26]; Arrays.setAll(d, k -> new ArrayList<>()); for (int i = 0; i < 26; ++i) { d[i].add(-1); } for (int i = 0; i < s.length(); ++i) { d[s.charAt(i) - 'A'].add(i); } int ans = 0; for (var v : d) { v.add(s.length()); for (int i = 1; i < v.size() - 1; ++i) { ans += (v.get(i) - v.get(i - 1)) * (v.get(i + 1) - v.get(i)); } } return ans; } } -
// OJ: https://leetcode.com/problems/unique-letter-string // Time: O(N^2) // Space: O(1) class Solution { public: int uniqueLetterString(string S) { int mod = 1e9 + 7, N = S.size(), ans = 0; for (int i = 0; i < N; ++i) { int cnts[26] = {0}, prev = 0, two = 0; for (int j = i; j < N && two != 26; ++j) { cnts[S[j] - 'A']++; int cur = prev; if (cnts[S[j] - 'A'] == 1) ++cur; else if (cnts[S[j] - 'A'] == 2) { --cur; two++; } ans = (ans + cur) % mod; prev = cur; } } return ans; } }; -
class Solution: def uniqueLetterString(self, s: str) -> int: d = defaultdict(list) for i, c in enumerate(s): d[c].append(i) ans = 0 for v in d.values(): v = [-1] + v + [len(s)] for i in range(1, len(v) - 1): ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i]) return ans -
func uniqueLetterString(s string) int { d := make([][]int, 26) for i := range d { d[i] = []int{-1} } for i, c := range s { d[c-'A'] = append(d[c-'A'], i) } ans := 0 for _, v := range d { v = append(v, len(s)) for i := 1; i < len(v)-1; i++ { ans += (v[i] - v[i-1]) * (v[i+1] - v[i]) } } return ans }