Substring

159, 340还有稍微复杂一些的76，全都是substring的题，解题方法也都是双指针，所以我把他们全放在后面的章节了。

239. Sliding Window Maximum

为了做substring后面的题，我先要啰嗦一下sliding window这道题。

这题暴力循环可以 O(nk)，heap 可以 O(nlog k)，deque 可以 O(n).

我们每一步要执行下面三个操作：

• 添加当前元素 nums[i];
• 删除指定元素 nums[i - k];
• 找到当前 window max;

暴力解法中，我们可以直接维护一个 list，每次操作都进行扫描，这样的复杂度是：

• Add O(1)
• Remove O(k)
• max O(k)

另一种选择是，维护一个 sorted list，这样的复杂度是：

• Add O(k)
• Remove O(k)
• max O(1)

再观察题目特性可以发现，我们在维护 sorted list 上有很多可以取巧的地方：

• 因为我们只关心每个 window 上的 max，因此没有必要把 window 内的所有元素都留着，在 Add 的时候可以直接把小于新元素的值都 pop 掉；
• 而在 remove 上，对最终结果会产生影响的，只有我们 remove 的元素就是 max 的情形，因为其他无关元素在 add 的时候就被拿掉了；因此我们可以存一个元素的相对位置，以此来判断我们要删掉的元素是不是当前的 max.
• 因为我们维护的是 sorted array ，max 依然是 O(1).
• 由于每一个元素只会被 add 和 remove 一次，整个流程的均摊复杂度就是 O(1).

要点：

• 维护一个可以双向操作的 sorted array.

• Deque 里面要存 index，而不是值，不然会出现 [8,1,2,8...] 这种情况下，我们有可能会把刚加进去的 8 又给拿出来的 bug.

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];

        int[] result = new int[nums.length - k + 1];
        // Deque stores indices of elements i, in descending order of nums[i]
        // First : smallet element in current window
        // Last : biggest element in current window
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < nums.length; ++i) {
            // if the new element is larger than the smallest element in deque
            // pull out all the elements that small than it
            while (!deque.isEmpty() && nums[i] > nums[deque.peekFirst()]) {
                deque.pollFirst();
            }
            deque.offerFirst(i);
            // When i - k == deque.peekLast(), it means that the last element has expired, 
            // it does not belong to the sliding window anymore, pull it out
            if (i - k == deque.peekLast()) deque.pollLast();
            // i - k + 1 means the index of max array of sliding window,
            // when it over 0, we start to add element into it
            if (i - k + 1 >= 0) result[i - k + 1] = nums[deque.peekLast()];
        }
        return result;
    }
}

3. Longest Substring Without Repeating Characters

说到这道题，就不得不说一下159了，说到159又不得不提到340。340是Google onsite最喜欢考的一道题。

• 给定一个长度为 n 的 String，它所有的 substring 数量是 n(n + 1) / 2 ，是一个 quadratic 的数量级。所以有些问题如果暴力遍历的话复杂度是没法让人满意的，某些问题如果用二维 DP 也至少需要 O(n^2) 的时间与空间开销。

• 给定一个长度为 n 的 String，切成若干个 pieces 总共有 2^{n-1} 种切法，即对于所有 n-1 个分界点上，选择“切/不切”.

• 此类问题最常用的优化，就是利用子串性质， abuse 子串的结构。

• 同时维护一个类似 sliding window 的结构去向尾部移动，如果是 KMP pattern matching，不回滚的 window / pattern 就可以达到 linear time.

在这个问题里，substring 里面一定没有重复字符，因此可以开一个 boolean array 作为 hash 记录 window 里面已经存在的字符。

同时如果在看到一个新字符之后出现重复的话，以这个字符为结尾的最长 substring 一定在 sliding window 里面同一个字符之后。

“必须以当前字符结尾” 是字符串问题中很常见的 optimal substructure, 因此这个问题也类似于 DP 问题。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1) return s.length();
        int start = 0;
        int end = 0;
        int max = 1;
        boolean[] hash = new boolean[256];
        while(end < s.length()){
            int key = (int) s.charAt(end);
            if(!hash[key]){
                hash[key] = true;
                end ++;
                max = Math.max(max, end - start);
            } else {
                while(start < end && s.charAt(start) != s.charAt(end)){
                    hash[(int)s.charAt(start)] = false;
                    start ++;
                }
                start ++;
                end ++;
            }
        }

        return max;
    }
}

当然这题双指针的解法更优更简单。后面双指针我也会放进去的。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) return s.length();
        int max = 1;
        int j = 0;
        boolean[] hash = new boolean[256];
        for (int i = 0; i < s.length(); ++i) {
            while (j < s.length()) {
                if (!hash[s.charAt(j)]) {
                    hash[s.charAt(j++)] = true;
                } else break;
            }
            max = Math.max(max, j - i);
            hash[s.charAt(i)] = false;
        }
        return max;
    }
}

383. Ransom Note

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) return false;
        if (ransomNote.length() == 0) return true;

        int[] hash = new int[256];
        int[] ran = new int[256];
        for (int i = 0; i < magazine.length(); ++i) {
            hash[magazine.charAt(i)]++;
        }
        for (int i = 0; i < ransomNote.length(); ++i) {
            ran[ransomNote.charAt(i)]++;
        }
        for (int i = 0; i < ran.length; ++i) {
            if (ran[i] > hash[i]) return false;
        }
        return true;
    }
}

459. Repeated Substring Pattern

有个trick就是要求的substring一定在几分之一处，因此我们就从2分之一开始找。

public boolean repeatedSubstringPattern(String str) {
    int l = str.length();
    for(int i=l/2;i>=1;i--) {
        if(l%i==0) {
            int m = l/i;
            String subS = str.substring(0,i);
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<m;j++) {
                sb.append(subS);
            }
            if(sb.toString().equals(str)) return true;
        }
    }
    return false;