UniqueLetterString [source code]
public class UniqueLetterString {
static
/****************************************************************************/
class Solution {
public int uniqueLetterString(String S) {
int N = S.length ();
int[][] look_left = new int[26][N], look_right = new int[26][N];
int[] next_index = new int[26];
Arrays.fill (next_index, -1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < 26; j++)
look_left[j][i] = next_index[j];
next_index[S.charAt (i) - 'A'] = i;
}
Arrays.fill (next_index, N);
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++)
look_right[j][i] = next_index[j];
next_index[S.charAt (i) - 'A'] = i;
}
long res = 0;
for (int i = 0; i < N; i++) {
res += (i - look_left[S.charAt (i) - 'A'][i]) * (look_right[S.charAt (i) - 'A'][i] - i);
}
return (int) (res % (1000_000_000 + 7));
}
}
/****************************************************************************/
public static void main(String[] args) {
UniqueLetterString.Solution tester = new UniqueLetterString.Solution();
String[] inputs = {
"BABABAB", "24",
"BABBABBBA", "33",
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String S = inputs[2 * i];
int ans = Integer.parseInt (inputs[2 * i + 1]), output = tester.uniqueLetterString (S);
System.out.printf ("%s\n%s\n%d\n",
S, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
感觉有点DP性质的题目, 相当难, 没戏;
contest结束的时候的AC rate也不是特别高, 算是难题了;
看看题目还是很有意思的一个题目, 大概看看例子, 感觉好像也能找到一点人逻辑; 不过后面看了一下答案给的解法, 全都是O(N)的解法, 这个就有点不可思议了;
自己写的时候突然意识到一个问题, 为什么他们的解法全都默认是S只有大写字母? 这个我翻了一下条件里面也没给啊?
这个要实现的是对应editorial2和discuss1的做法; 前者具体实现方式是一个维护c=list of index of c这样的map of lists这样的结构, 后者是用一个维护 last two occurrences的方法;
我想要用左右lookup的方法来做; 主要是这个思路我比较熟悉; 但是做不到1pass了; 实际上awice那个做法也很好理解和掌握;
突然发现简单的比如lookleft好像并不好实现? 比如一开始N=10, 然后对于A的这10个, 全都是-1, 然后你在[3]看到了A, 然后呢? 这时候[4..9]应该都更新到A, 但是这个你怎么做? 肯定不能eager的做, 不然复杂度就上去了;
感觉还要单独维护一个专门的26个rightmost index, 这样才好更新left_look这个数组;
neighbor index lookup
again, 实际上还是下面editorial2这个做法更加简单: 只是单纯的lookup next occurrence, 实际上只要sparsify这样的一个list of indexes, 就行了; 不用用这个DP lookup这样的结构;
我这里还是用这个方法写写看, 展示一下这个思路;
最后是比较轻松的AC了; 速度是83(NA).
注意这里next_index的定义; 比如如果我3, 6, 9是A, 那么我给lookleft[A][6]存的应该是3, 给lookright[B][6]存的应该是9, 这样我后面计算的时候方便一点; 对应的, 看我头两个循环里面, 到底是先更新nextindex, 还是先把nextindex给赋值给当前的column;
我感觉我这个写法还是挺好理解的;
editorial
Approach #1: Maintain Answer of Suffix [Accepted]
这个做法awice解释的还是非常好的; 至少algorithm第一段结束还是很清楚的; 第二段开始突然冒个F出来, 后面又有peek, 就不知道是什么了;
不过algorithm部分最后一部分还是不是很看得懂; again, 这个也是awice的风格了, algorithm部分基本他就是在解释代码, 而不是在讲思路了, 所以先大概看一下代码, 不懂的回头再来看他是怎么解释的;
不过还是学习一个, 你看awice写算法的时候, 也是从具体的例子来出发的: 对应于这个例子, 每一个所涉及的数据结构是什么state, 都计算出来, 方便捋清楚代码;
class Solution {
Map<Character, List<Integer>> index;
int[] peek;
int N;
public int uniqueLetterString(String S) {
index = new HashMap<> ();
peek = new int[26];
N = S.length();
for (int i = 0; i < S.length(); ++i) {
char c = S.charAt(i);
index.computeIfAbsent(c, x-> new ArrayList<Integer>()).add(i);
}
long cur = 0, ans = 0;
for (char c: index.keySet()) {
index.get(c).add(N);
index.get(c).add(N);
cur += get(c);
}
for (char c: S.toCharArray()) {
ans += cur;
long oldv = get(c);
peek[c - 'A']++;
cur += get(c) - oldv;
}
return (int) ans % 1_000_000_007;
}
public long get(char c) {
List<Integer> indexes = index.get(c);
int i = peek[c - 'A'];
return indexes.get(i+1) - indexes.get(i);
}
}
第一个循环建立index这个反向查询;
诶, 奇怪啊:
for (char c: index.keySet()) {
index.get(c).add(N);
index.get(c).add(N);
cur += get(c);
}
这是什么梗啊, 直接get(c)是什么啊? 哦, 下面定义了一个函数, 哎, 这个命名真的是太坑了, 故意的吗; 非要跟Map的get一个名字;
在第二个循环这里get出来的都是[1] - [0]这个, 因为这个时候get函数里面的i都是0, 因为peek还没有被改变;
这算法好复杂, 怎么uwi几句话就写完了?
这个算法看起来复杂是因为虽然只有两个循环, 但是实际上是有好几条平行进行的运算, 你看ans也一直在更新, cur也一直在更新, 然后peek这个也一直在更新;
对于这种, 我以前没有总结过; 这种算法, 看的时候, 就按照Guoye看算法的那种方式, 如果直接看procedure看不懂是在干什么, 那么直接就trace value, 对于比如这里, 三个在一直更新的ans, cur, peek, 按顺序一个一个的看, 是怎么被更新的;
当然, 具体来说还是要结合例子来看; 然后有时候可能一个pass还是看不懂, 那么就来回的穿插重复就行了;
他这里这个get完全没有必要独立出去当成一个自己的函数: 大量依赖global变量的函数, 真的是非常降低readability;
感觉这个peek就是对每一个c维护了一个顺序在indexes里面取interval的操作? 最好还是自己用一个例子来试试看;
哦, 突然想起来, algorithm里面后半段提到的F, 前面是有定义的, 我自己忘记了;
重新回头看他上面的解释, U(S) = sum U(c, S) for c in A, 是一个类似marginalization的操作;
algorithm第一段是在解释怎么calculate F(i) for each c (for all i);
他intuition一开始先理解这里这个问题, 因为是一个要遍历所有的substring的问题, 所以他先观察, 用另外一个角度来理解substring这个概念; 因为希望用类似DP的思路去加速, 所以用了一个类似root involvement的思路, 给F加了一个参数, 也就是start index, 类似于强行加维度: 这个也是DP里面常见的; 当然, 常见不代表简单, 事实上, 这个是一个相当难掌握的技巧;
然后intuition其他部分就不难理解了; U可以sum这个很好理解;
然后algorithm第一段不太好理解; 对于一个substring x, 我们希望知道他有多少个unique char, 那么当我们只考虑针对比如'A', 那么我们应该问x什么? 'A'在里面是否是unique的? 这样对26个char都问过了之后, 我们就知道U(x)的答案了: 注意了, 很自然的, 这个答案, for any x, 是在0..26的范围内的; 这题因为我没有做, 所以连这一步其实都没有分析到;
again, to recap, you have to ask x: is 'A' unique in you?
然后他举了一个S[10] = S[14] = S[20] = "A"的例子; 然后说, i=8的时候, answer是4, 这个是什么意思? 这个answer指的是什么? 应该就是F(8). 那么好理解, when I ask all x that starts at 8, whether 'A' is unique in it, 事实上就是意思是'A'要在x里面出现1次: 不是0次, 也不是超过1次; 然后用S[10] = S[14] = S[20] = "A"这个信息, 就很好计算了, 8..10, 8..11, 8..12, 8..13这几个都是可以让'A' unique的subtring that starts at 8. 这一段就没问题, 解决一个小问题;
然后说F(0, c) = index[c][1] - index[c][0], 这个事实上也不是很好理解, 事实上, 这个是对上面这个计算的一个敏锐的总结: 并不trivial; 知道建立一个char->index的反向查询, 然后知道怎么用这个反向查询来计算这里要的这个类似上面的4的这个结果, 还是有点难度的; 拓展开来, F(i, c)怎么计算? 应该是计算从i之后的c第二次出现的index减掉c第一出现的index; 这个应该是有办法维护的; 事实上, 一个很简单的向右lookup数组应该就可以维护;
然后algorithm第三段, final answer是sum F(i), 这个也是正确的; 毕竟i是我们故意加出来的一个维度, 现在要marginalize掉;
上面慢慢分析过来之后, 第三段其实也看懂了; 当然为什么要说是2pointer? 感觉没啥关系啊; 这个算法其实就是各种tricky的历史信息难以维护; 另外, 我上面一段总结了一个F(i, c)的计算, 他还没有提到具体怎么实现, 但是他这里既然已经开始sum F(i)了, 估计是他是有自己的方法, 考虑过这个计算的了;
哦, 最后一段就介绍了怎么计算这个, 这个peek就是一个类似向右找的操作; 具体怎么定义的还不好说, 不过应该是这么一回事; 然后可以很自然的看代码了, 至少知道他的大概思想是什么意思了;
这个算法还是比较复杂的, 但是awice介绍的却非常详细到位, 估计是他自己想出来的; 毕竟他很强, 想出来这种绕人的算法对他来说还是挺正常的. 反而往往是他看来然后改写的算法, 都讲的比较糟糕, 类似之前那个拼图题;
大概思考了一下, 我还是不喜欢他这个peek的计算方式, 直接计算一个, 针对每一个index i的结果就是了; 我自己后面考虑用这个方式实现一下? 还没有想好, 毕竟awice这个算法真的是有点复杂的;
暂停一蛤;
这个题目自己完全没有尝试过, 感觉还是, 直接看别人的答案完全看的不得要领;
首先, 我们看看, 笨办法我自己会怎么做? 我肯定说, 是N^2 * N; 但是笨办法实际上是N^2: 按照awice这里的介绍, 你只要先for each start index, 然后直接走一个O(N)到头的for each end index, 如果当前start..end满足没有重复, 就可以了;
然后我们想了这个笨办法之后, 才开始理解这个问题的本质; 这个笨办法对应的就是awice intuition第一段说的这个F(i)函数;
awice也说了, 如果计算F(i)是要用O(N), 那么这个对应的就是bruteforce做法, 是O(N^2);
那么这个时候他就开始换一个角度来思考这个问题; 对于某一个substring x而言, 我们用一个类似aggregate的思路去理解这个问题; x最后得几分, 实际上是类似于一个对26个c, 分别考虑, 能否在这个c上面得分, 有点类似sum indicator(c is unique in x) for c in A这样的算法; 这个indicator类似之前说过的U(x, c)这个函数(取值是0/1);
到这个时候为止, 我们还是没有想到怎样更快的计算F(i). 最后的关键就是, 一个一个的计算F(i), 几乎是无法加速的; 我们的关注点, 干脆就转换到c上面来;
对于一个c, 比如说是A, 比如他出现在10, 14, 20这三个index, 那么最后有哪些x能够从A身上拿分, 我们是很容易计算的; 所有(0..9, 11..13)的x, 肯定都是能在A上面拿分的, 然后(10, 11..13), (0..9, 10)这几个也能在A拿分; 合起来, 好像是(0..10, 10..13)的, 都可以在A拿分, 那么这样的x, 总共有(10 - (-1)) (14 - 10)个. 这个是所有能在[10]这个A上面拿分的; 对应的, 后面能在[14]这个A上面拿分的, 也可以用一样的方法计算: (14 - 10) (20 - 14). 可以看到这个计算形式是完全类似的;
好了, 对于每一个A, 我们知道how many x such that this A can make it get 1 point. 这个其实如果你遍历所有x, 并且合计他们在这个A上面的得分的话(1 or 0), 跟这个结果是一样的; 这样解释下来, 应该就可以知道最后只要我们把所有的三个A可以贡献的x的count都统计一下, 能够从A上面的所有x的个数, 也就是所有A可以贡献给总分的数量, 就知道了;
他这里这个peek我回头想想, 其实是设计的没有问题的, 比如这里我们index[A] = [10, 14, 20, N, N], 这个实际上我们就是要会用每一个interval这样的计算; 另外一个需要注意的是, 上面只是针对A讨论, 但是实际上, S的每一个位置都是一个c, 所以最后我们并不需要区分这个c是多少, 直接S走一遍, 然后看看这个c是多少, 然后看看index[c]走到什么位置了(根据peek)就行了;
现在回过头来看代码, 感觉他的计算过程跟我上面描述的不太一样; 我的描述是用了乘法的, 但是他实际的循环代码里面是没有乘法的;
不是很理解, 打trace;
index: {A=[1, 4, 8], B=[0, 2, 3, 5, 6, 7]}
char:(A), cur:(3)
char:(B), cur:(5)
index: {A=[1, 4, 8, 9, 9], B=[0, 2, 3, 5, 6, 7, 9, 9]}
char:(B), cur:(4), ans:(5), peek:
char:(A), cur:(5), ans:(9), peek:
char:(B), cur:(6), ans:(14), peek:
char:(B), cur:(5), ans:(20), peek:
char:(A), cur:(2), ans:(25), peek:
char:(B), cur:(2), ans:(27), peek:
char:(B), cur:(3), ans:(29), peek:
char:(B), cur:(1), ans:(32), peek:
char:(A), cur:(0), ans:(33), peek:
BABBABBBA
33
33
打了trace之后, 方便理解他的每一个变量的意思; 他这个cur和ans记录的到底是什么, 他的解释里面是没有的;
awice现在写editorial越来越绕人了, 现在他的文章下面的回复数量明显减少, 感觉很多人都是看不懂就懒得看了; 毕竟现在discuss好的解法也有很多; awice比如这个editorial1, 面试的时候能指望自己讲清楚吗;
我们看看, 第三个循环开始之前, cur就有2+3=5, 其中A贡献了3, B贡献了2, 意思就是我们现在认为有两个substring可以从第一个B拿分, 有3个substring可以从第一个A拿分. 这些substring分别是哪些?
他这个算法还有一个难懂的地方是他非要把ans错开一个iteration更新; 更好的方法是第二个循环结束之后立刻把这个当前的cur=5给丢到ans里面, 然后第三个循环直接就是cur更新完了立刻就在当前iteration的末尾更新ans, 这样比较好; 他这个错开更新ans, 完全就是炫技, 想要省几行代码; 其实就省了一行;
进入第三个循环, [2]这个B出现了, 然后这个B实际上只能让一个substring(他自己)拿分; 所以这个时候你看到cur减少了1(cur是所有的c当前拿到的分的总和, 这里B减少了1分, 其他的都是不变的, 也就是他algorithm后面说的只有B变动这里, 所以最后cur-1), 然后这个cur又被统计进去到了ans里面(5 + 4 = 9);
所以他这个cur可能就是一个F(i)的功能? 也不完全是, 不然的话第三个循环开始之前, F(0)应该只有B的得分.
我感觉他这个cur应该计算的就是一个对于所有的c, 当前peek对应的这些c的贡献; 比如最开始, 所有peek[c]都是0, 所以cur就是5: index[A][1] - index[A][0] + index[B][1] - index[B][0], 也就是第一个A开头的能拿分的substring个数, 然后第一个B开头的能拿分的substring的个数;
这里你可能闻到一个问题, 比如0..1的这个BA, 为什么没有算到A的贡献里面去? 感觉应该是一个去重的需要; 每一个c occurrence, 只向后看, 自己能管上多少个substring; 也不对啊, BA理所应当能够那2分的, 就算是B算过他之后A又算了他, 也不能说是重复啊?
上面这个trace的ans可以不看了, 反而很迷惑人, 你就记得最后这个33的答案实际上是所有的cur加起来的结果;
java> 4 +5 +6 +5 +2 +2 +3 +1 +0
java.lang.Integer res3 = 28
加上最开始的5, 就是33;
所以关键是搞懂这个cur是在计算的什么;
更新cur的操作其实不是特别复杂, 每一个循环最后cur的这个+=diff, 实际上就是把, 比如当前iteration扫到的是A, 那么就用A的下一个gap替换目前正在cur里面参与计算的gap;
不过这个计算背后的原理到底是什么呢;
你看这个图, 最不可思议的一个地方, 对于每一个occurrence, 实际上这个occurrence所lead的这个group, 是至少参与了两次计算的: 这里A的这个4, 甚至参与了3次计算: 注意这三次都是贡献给了ans里面去的;
好像大概理解了一点他的意思; 比如你看这个橙色的4, 这个是针对[4]的这个A的, 这个4代表的实际上就是我上面的乘法计算里面的右边因子; 那么左边因子呢? 实际上, 你看这里橙色4一共参与了3次ans的计算, 对应的就是左边因子; 不信你看, [4]之前的A在[1], 所以4-1=3, 如果按照我的乘法计算, 最后[4]这个A的贡献, 我的计算方法也就是(4 - 1) (8 - 4), 跟这里最后的结果是一模一样的;
你可以验证一下他其他的地方的计算, 都是等价的, 包括深绿色的这个2, 对应的是一个1 2的计算(因为[3]这个B左边到上一个B的距离只有1), 等等;
那么我是知道了, 他这个做法跟我的乘法做法其实是等价的;
TODO:
不过他这个加法到底是什么思路? 尤其是为什么要维护这样的一个cur?
暂时还是无法理解, 先摆着了; 至少我知道一个可行的做法了;
在他帖子底下留了一个回复, 开了邮件提醒, 先等等看了;
Approach #2: Split by Character [Accepted]
好像就是我上面说的乘法思路;
class Solution {
public int uniqueLetterString(String S) {
Map<Character, List<Integer>> index = new HashMap();
for (int i = 0; i < S.length(); ++i) {
char c = S.charAt(i);
index.computeIfAbsent(c, x-> new ArrayList<Integer>()).add(i);
}
long ans = 0;
for (List<Integer> A: index.values()) {
for (int i = 0; i < A.size(); ++i) {
long prev = i > 0 ? A.get(i-1) : -1;
long next = i < A.size() - 1 ? A.get(i+1) : S.length();
ans += (A.get(i) - prev) * (next - A.get(i));
}
}
return (int) ans % 1_000_000_007;
}
}
这个方法我上面已经分析过了, 所以几乎没有理解难度; 完全简单的多;
这个解法的原作者是lee, 有人说discuss里他的解释更加好, 去看看先;
https://leetcode.com/problems/unique-letter-string/discuss/128952/One-pass-O(N)-Straight-Forward
Intuition:
Let's think about how a character can be found as a unique character.
Think about string "XAXAXXAX" and focus on making the second "A" a unique character.
We can take "XA(XAXX)AX" and between "()" is our substring.
用的例子都跟我测试awice解法的时候自己想的例子很类似;
again, 真正面试的时候就有体现, 想typical例子的能力, 反而是一个很重要, 但是在LeetCode刷题的时候很容易被忽视的能力;
We can see here, to make the second "A" counted as a uniq character, we need to:
- insert "(" somewhere between the first and second A
- insert ")" somewhere between the second and third A
For step 1 we have "A(XA" and "AX(A", 2 possibility.
For step 2 we have "A)XXA", "AX)XA" and "AXX)A", 3 possibilities.So there are in total 2 * 3 = 6 ways to make the second A a unique character in a substring.
In other words, there are only 6 substring, in which this A contribute 1 point as unique string.Instead of counting all unique characters and struggling with all possible substrings,
we can count for every char in S, how many ways to be found as a unique char.
We count and sum, and it will be out answer.
大概是这个意思了, 还是很好理解的; 关键点就是站在char的贡献能力的角度去思考, 而不是站在审查每一个substring的角度去思考;
Explanation:
- index[26][2] record last two occurrence index for every upper characters.
- Initialise all values in index to -1.
- Loop on string S, for every character c, update its last two occurrence index to index[c].
- Count when loop. For example, if "A" appears twice at index 3, 6, 9 seperately, we need to count:
- For the first "A": (6-3) * (3-(-1))"
- For the second "A": (9-6) * (6-3)"
- For the third "A": (N-9) * (9-6)"
Complexity:
One pass, time complexity O(N).
Space complexity O(1).
没仔细看了, 应该就是维护一个向左向右的lookup的结构就行了; 注意初始值, 这个awice的解法里面有解释, 最好的办法是左边尽头的初始值是-1, 右边尽头的初始值是N, 这样计算的时候根本不用管; 比如长度10, 你在7有一个A, 那么这个A的右边因子, 直接就是10 - 7, 管都不用管的, 只要look_right[8..9]你存的都是10(初始值)的话;
public int uniqueLetterString(String S) {
int[][] index = new int[26][2];
for (int i = 0; i < 26; ++i) Arrays.fill(index[i], -1);
int res = 0, N = S.length(), mod = (int)Math.pow(10, 9) + 7;
for (int i = 0; i < N; ++i) {
int c = S.charAt(i) - 'A';
res = (res + (i - index[c][1]) * (index[c][1] - index[c][0]) % mod) % mod;
index[c] = new int[] {index[c][1], i};
}
for (int c = 0; c < 26; ++c)
res = (res + (N - index[c][1]) * (index[c][1] - index[c][0]) % mod) % mod;
return res;
}
看他第一个循环, 比如就是他说的, 3, 6, 9分别都有A, 那么:
- i = 3, 计算的是(3 - (-1)) * ((-1) - (-1)) = 0
- i = 6, (6 - 3) * (3 - (-1))
- i = 9, (9 - 6) * (6 - 3)
好像是没什么问题; 但是最后这个(N - 9) * (9 - 6)是什么时候计算的? 因为他实际上是只维护左边两个occurrence的index的; 你看他也没什么收尾操作啊;
哦, 有单独的收尾; 第二个循环干的就是这个, 那没什么问题的了;
这个算法的计算也有一个错位, 比如在[9]计算的实际上是[6]这个A的所有的贡献, 不过这个错位比较简单, 整体是很好理解的;
TODO
这个帖子的评论还没有看;
UNFINISHED
uwi: 3min
class Solution {
public int uniqueLetterString(String S) {
char[] s = S.toCharArray();
int n = s.length;
int mod = 1000000007;
long ret = 0;
for(int i = 0;i < s.length;i++){
int l = i-1;
for(;l >= 0 && s[l] != s[i];l--);
int r = i+1;
for(;r < n && s[r] != s[i];r++);
ret += (long)(r-i)*(i-l);
}
return (int)(ret%mod);
}
}
还是类似的思路, 不过他当时好像是想冲时间, 所以你看他l和r直接是本地计算的, 而不是提前计算好; 然后估计他看这个时间速度能够AC, 就懒得优化了;
Problem Description
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, 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, retrun 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.
Difficulty:Hard
Total Accepted:279
Total Submissions:1.5K
Contributor:lee215
Companies
forusall
Related Topics
two pointers