Amazon Online Assessment OA 刚做完，把题目分享给大家，换点大米

先说结论，两题没做完，只完成第一题，第二题更简单本应该先做的，但最后时间不够了。
所以应该是已经挂了，分享给大家看看，有没有遇到原题，我是没搜出来，测试的时候也不敢把窗口切来切去的。

FridaW 发表于 2021-9-24 00:36
感谢楼主，祝找工顺利！我第一题只想到每次遍历去掉首尾，请问大佬们还有更加优化的解法吗？

第一题先用快慢指针分两半，然后把后半段reverse，然后再两个list相加。

谢谢楼主分享。
第二题O(n)应该可以做：
       public int passwordStrength(String s) {
        int n = s.length();
        int[] last = new int[26];
        Arrays.fill(last, -1);
        int ans = 0;
        int cur = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) -'a';
            cur += i + 1 - (last[index] + 1);
            ans += cur;
            last[index] = i;
        }
        return ans;
    }
    dp[i]: number of distinct letters for all substring end at i
    last[i]: last index for each letter
    There are total (i + 1) substring at [0, i]. letter i add at most i + 1 new distinct letter in dp[i]
    also need to substract previous substring count which already having letter i, which is lastIndex + 1
     dp[i] = dp[i - 1] + i + 1 - (lastIndex + 1) => cur = cur + i + 1 - (lastIndex + 1)
    Time complexity: O(n)
    Space complexity: O(1)

SteinGate 发表于 2021-11-12 20:31
这题和828还不一样。感觉828比这题难不少。我们来看一个例子就知道了。
828的要求：
For example if s  ...

如果只记录一次，应该更简单
dp[ i ] 代表从0开始 以 i 坐标结尾的substring的所有substring的unique 和

dp[ i ] = dp[i - 1] + (i - last occurance of s.charAt( i ))  （meaning number of new uniques the new s.charAt( i ) can contribute to dp[ i - 1]）
一个长26的数组记录 并更新 last occurance of s.charAt( i )
dp只用两个数组不断更新就行

谢谢分享 zszszs

感谢楼主分享，找工加油！

谢谢分享

请问楼主是intern吗

这个太赞了！感谢！

感谢分享

谢谢分享! 第二个问题是 LC828

楼主是校招还是社招啊？

感谢分享，第二题的时间复杂度是多少呢？

补充内容 (2021-09-24 02:02 +08:00):
只能想到O（n^2）的方法，有更好的吗