Skip to content

Latest commit

 

History

History
169 lines (142 loc) · 5.86 KB

0828._Unique_Letter_String.md

File metadata and controls

169 lines (142 loc) · 5.86 KB

828. Unique Letter String

题目: https://leetcode.com/problems/unique-letter-string

难度: Hard

题意:

  1. 求一个字符串中的所有非空子字符串,这些字符串当中的唯一字符数的总和
  2. 唯一字符数就是在字符串中出现只有一次的字符的个数

思路:

  • 枚举左右端点,暴力统计子字符串的唯一字符数,复杂度是o(n^3)
  • 枚举左端点,然后遍历右端点,每次保存上一次的字符统计个数,和唯一字符数,并更新为当前的数值,复杂度是o(n^2)
  • 注意到,当某个字符出现次数大于1个后,后面不管怎么遍历,该字符都不会是唯一字符,因此,有个剪枝动作,如果此时某个字符出现次数大于1个后,后面直接跳过该字符
  • 因此我们需要实现把每个字符出现的位置记录下来,以便可以跳过某些字符
  • 枚举左端点,然后遍历右端点,加上剪枝之后,每个字符至多被扫描2次。把字符串拆成26个字符后,从左边遍历到右边,就需要一个堆来维持,类似于归并排序的merge操作,这个堆最多26个元素,时间复杂度是o(52nlog26)
  • 我们可以另外想一种解决方案。假设我们把26个字母全部拆开,当某个字符第一次出现到第二次出现中间,它就能贡献一个唯一字符。假设A这个字符,第一次出现是位置1,第二次出现是位置10,于是1-10中间就可以增加一个唯一字符,同理,其他字符也是这样的。假设左端点移动,所需要改变的,也只有一个字符而已,这个字符的第一次出现的位置,到第二次出现的位置,改变了位置。我们不要想着每个字符串有多少唯一字符,而是从总体来看,每个字符贡献了多少次唯一字符。还是上面那个例子,A这个字符,第一次出现是位置1,第二次出现是位置10,那么贡献了10-1=9次唯一字符。扫描左端点时,只需要不断用上一个左端点字符移动来更新总唯一字符数即可。复杂度是o(n)

解法一:

class Solution {
	 private class Item implements Comparable<Item> {
        int alph;
        int idx;
        int pos;

        public Item(int alph, int idx, int pos) {
            this.alph = alph;
            this.idx = idx;
            this.pos = pos;
        }

        @Override
        public int compareTo(Item o) {
            return Integer.compare(pos, o.pos);
        }
    }

    private int solve(List[] idxList, int start, int len, int[] init) {
        PriorityQueue<Item> queue = new PriorityQueue<Item>();
        boolean[] flag = new boolean[26];
        for (int i = 0;i < 26;i++) {
            flag[i] = false;
        }
        int ret = 0;
        int res = 0;
        int pre = start - 1;

        for (int i = 0;i < 26;i++) {
            int idx = init[i];
            if (idx != idxList[i].size()) {
                queue.add(new Item(i, idx, (Integer) idxList[i].get(idx)));
            }
        }

        while (!queue.isEmpty()) {
            Item top = queue.poll();
            ret += (long) res * (top.pos - pre) % MOD;
            if (ret >= MOD) {
                ret -= MOD;
            }
            if (flag[top.alph]) {
                res--;
            } else {
                flag[top.alph] = true;
                if (top.idx + 1 != idxList[top.alph].size()) {
                    queue.add(new Item(top.alph, top.idx + 1, (Integer) idxList[top.alph].get(top.idx + 1)));
                }
                res++;
            }
            pre = top.pos;
        }

        ret += (long) res * (len - pre) % MOD;
        if (ret >= MOD) {
            ret -= MOD;
        }
        return ret;
    }

    private static int MOD = 1000000007;

    public int uniqueLetterString(String S) {
        List[] idxList = new List[26];
        int[] init = new int[26];
        for (int i = 0;i < 26;i++) {
            idxList[i] = new ArrayList<Integer>();
            init[i] = 0;
        }
        for (int i = 0;i < S.length();i++) {
            idxList[S.charAt(i) - 'A'].add(i);
        }

        int ret = 0;
        for (int i = 0;i < S.length();i++) {
            ret += solve(idxList, i, S.length(), init);
            if (ret >= MOD) {
                ret -= MOD;
            }
            init[S.charAt(i) - 'A']++;
        }

        return ret;
    }
}

解法二:

class Solution {
	 private static int MOD = 1000000007;

    public int uniqueLetterString(String S) {
        List<Integer>[] idxList = new List[26];
        int[] pos = new int[26];
        for (int i = 0;i < 26;i++) {
            idxList[i] = new ArrayList<Integer>();
            pos[i] = 0;
        }
        for (int i = 0;i < S.length();i++) {
            idxList[S.charAt(i) - 'A'].add(i);
        }

        int ret = 0;
        int res = 0;
        for (int i = 0;i < 26;i++) {
            if (pos[i] < idxList[i].size()) {
                if (pos[i] + 1 < idxList[i].size()) {
                    res += idxList[i].get(pos[i] + 1) - idxList[i].get(pos[i]);
                } else {
                    res += S.length() - idxList[i].get(pos[i]);
                }
            }
        }

        for (int i = 0;i < S.length();i++) {
            ret += res;
            if (ret >= MOD) {
                ret -= MOD;
            }
            int j = S.charAt(i) - 'A';
            if (pos[j] + 1 < idxList[j].size()) {
                res -= idxList[j].get(pos[j] + 1) - idxList[j].get(pos[j]);
            } else {
                res -= S.length() - idxList[j].get(pos[j]);
            }
            pos[j]++;
            if (pos[j] < idxList[j].size()) {
                if (pos[j] + 1 < idxList[j].size()) {
                    res += idxList[j].get(pos[j] + 1) - idxList[j].get(pos[j]);
                } else {
                    res += S.length() - idxList[j].get(pos[j]);
                }
            }
        }

        return ret;
    }
}