Google 2016 面试题 | 数组补丁

Posted on   |   In   |     |  


From jiuzhang

题目描述

给定一个字符串，找到最长的包含最多k个不同字符的子串，输出最长子串的长度即可。

Example：
给出字符串”eceba”，k = 2
输出答案3，最长包含最多2个不同字符的子串为”ece”

解题思路

最暴力的做法是穷举所有可能的子串，一共有n^2级别个不同的子串，然后对于每一个子串统计有多少不同的字符，如果少于k个就更新答案。这是一个三重循环的穷举，复杂度是O(n^3)。聪明的读者肯定想到了第二重和第三重循环可以合并，因为之前的统计信息可以继续使用而不需要每一次重新统计。这样的话穷举子串的开始位置和结束位置，复杂度是O(n^2)。如果在面试时提出了这个算法，面试官首先会表示认同，然后希望你进行优化。我们来看看如何进行优化。

在统计的过程中我们可以发现，当穷举的开始位置改变时我们会选择重新统计，但其实当开始位置改变时，我们之前记录的大部分信息都是有用的，我们只需在原有的统计结果上稍作修改。我们在两层for循环的时候其实会发现我们内层的fo循环其实并不需要每次都再重复遍历。比如外层for循环指针i每次向前移动变成i+1的时候，内层for循环的j没必要每次都退回到i的位置，其实是可以保留在j的位置不变的。因为可以证明对于从i+1到j-1这些情况都不会出现重复的元素，所以我们只用考虑从i+1到j就可以了。

分析一下这个算法的时间复杂度，虽然我们会用到两重循环（请看参考程序），但是因为这两个指针只增不减，每次循环指针增加1，因此while循环总共只会进入n次（n = s.length( ))，所以时间复杂度是O(n)。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution{
  /**
   * @param s: A string
   * @return : The length of the longest substring
   *           that contains at most k distinct characters.
   */
   public int lengthOfLongestKDistinct(String s, int k){
     int maxLen = 0;
     // Key: letter; value: the number of occurrences.
     Map<Character, Integer> map = new HashMap<Character, Integer>();
     int i, j = 0;
     char c;
     for (i = 0; i < s.length(); i++){
       while (j < s.length()){
         c = s.charAt(j);
         if(map.containsKey(c)){
           map.put(c, map.get(c) + 1);
         } else {
           if (map.size() == k)
             break;
           map.put(c, 1);
         }
         j++;
       }

       maxLen = Math.max(maxLen, j - i);
       c = s.charAt(i);
       if(map.containsKey(c)){
         int count = map.get(c);
         if (count > 1) {
           map.put(c, count - 1);
         } else {
           map.remove(c);
         }
       }
     }
     return maxLen;
   }
}

算法分析

这是一道很有区分度的题目，有O(n^3),O(n^2),O(nlogn)（follow up）,O(n)时间复杂度的做法。先提出一种可行算法，通过一步步分析、优化，最后提出O(n)的最优算法并完成代码就可以达到hire的程度。

相关练习

minimum-size-subarray-sum
longest-without-repeating-characters