Top K Character Scores
You are given a string s and an array of integers scores, where scores[i] represents the individual score of the character s[i]. Your task is to find the maximum total score achievable by selecting at most k distinct characters from the string. When a character is selected, all its occurrences in the string s contribute their individual scores from the scores array to the total sum.
[ "abacaba", "[1,2,3,4,5,6,7]", "2" ]
Explanation. Character 'a' appears at indices 0, 2, 4, 6. Scores: 1, 3, 5, 7. Total 'a' score = 1+3+5+7 = 16. Character 'b' appears at indices 1, 5. Scores: 2, 6. Total 'b' score = 2+6 = 8. Character 'c' appears at index 3. Score: 4. Total 'c' score = 4. Sorted unique character scores: [16 ('a'), 8 ('b'), 4 ('c')]. Since k=2, we select the top 2 scores: 16 + 8 = 24.
[ "zzzaac", "[10,20,30,1,2,5]", "3" ]
Explanation. Character 'z' appears at indices 0, 1, 2. Scores: 10, 20, 30. Total 'z' score = 10+20+30 = 60. Character 'a' appears at indices 3, 4. Scores: 1, 2. Total 'a' score = 1+2 = 3. Character 'c' appears at index 5. Score: 5. Total 'c' score = 5. Sorted unique character scores: [60 ('z'), 5 ('c'), 3 ('a')]. Since k=3, we select the top 3 scores (all unique characters): 60 + 5 + 3 = 68.
[ "aaaaa", "[10,1,2,3,4]", "1" ]
Explanation. Character 'a' appears at indices 0, 1, 2, 3, 4. Scores: 10, 1, 2, 3, 4. Total 'a' score = 10+1+2+3+4 = 20. Since k=1, we select 'a'. Total score = 20.
[ "banana", "[1,2,3,4,5,6]", "1" ]
Explanation. Character 'b' appears at index 0. Score: 1. Total 'b' score = 1. Character 'a' appears at indices 1, 3, 5. Scores: 2, 4, 6. Total 'a' score = 2+4+6 = 12. Character 'n' appears at indices 2, 4. Scores: 3, 5. Total 'n' score = 3+5 = 8. Sorted unique character scores: [12 ('a'), 8 ('n'), 1 ('b')]. Since k=1, we select the highest score: 12.
[ "topcoder", "[10,1,10,2,1,5,20,3]", "10" ]
Explanation. Unique character scores: 't': index 0. Score: 10. 'o': indices 1, 3. Scores: 1, 2. Total 'o' score = 1+2 = 3. 'p': index 2. Score: 10. 'c': index 4. Score: 1. 'd': index 5. Score: 5. 'e': index 6. Score: 20. 'r': index 7. Score: 3. Sorted unique character scores: [20('e'), 10('t'), 10('p'), 5('d'), 3('o'), 3('r'), 1('c')]. There are 7 unique characters. Since k=10 is greater than 7, we sum all unique character scores: 20 + 10 + 10 + 5 + 3 + 3 + 1 = 52.
Follow-up: Can you solve this problem if `s` could contain uppercase letters and digits as well, and `k` could be larger (up to the total number of unique characters)?
- `1 <= s.length <= 10^5` - `s.length == scores.length` - `s` consists of lowercase English letters. - `1 <= scores[i] <= 100` - `1 <= k <= 26` (since there are only 26 lowercase English letters)
- Views
- 12