Daily LeetCode – day0039 0828. Count Unique Characters of All Substrings of a Given String

// 0828. Count Unique Characters of All Substrings of a Given String
class Solution {
    public int uniqueLetterString(String s) {
        ArrayList<ArrayList<Integer>> lettersPositions = new ArrayList<>();
        for (int i = 0; i < 26; ++i) lettersPositions.add(new ArrayList<>());
        char[] charArray = s.toCharArray();
        int length = charArray.length;
        for (int i = 0; i < length; ++i) lettersPositions.get(charArray[i] - 65).add(i);
        int ans = 0;
        for (ArrayList<Integer> letterPositions : lettersPositions) {
            int size = letterPositions.size();
            if (size != 0) {
                if (size == 1) {
                    ans += (letterPositions.get(0) + 1) * (length - letterPositions.get(0));
                } else {
                    ans += (letterPositions.get(0) + 1) * (letterPositions.get(1) - letterPositions.get(0));
                    for (int i = 1; i < size - 1; ++i) ans += (letterPositions.get(i) - letterPositions.get(i - 1)) * (letterPositions.get(i + 1) - letterPositions.get(i));
                    ans += (letterPositions.get(size - 1) - letterPositions.get(size - 2)) * (length - letterPositions.get(size - 1));
                }
            }
        }
        return ans;
    }
}
学习笔记:
这是一道困难题,难在想到要求出每一个字符的价值。
其实每个字符的价值就是上一次出现的差,还有下一次出现的差。如果没有出现,那就是-1和length。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注