唯一字母串-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
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)

解法一：

```java
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;
    }
}
```

解法二：

```java
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;
    }
}
```

该分类下的相关小册推荐：

数据结构与算法之美

编程之道-算法面试(下)

业务开发实用算法精讲

数据结构与算法(下)

数据结构与算法(上)

算法面试通关 50 讲

编程之道-算法面试(上)