从O（n^3）到O（n^2）到O（n）逐步优化
package com.graph; import java.util.*; import org.omg.CORBA.INTERNAL; public class Solution { //TC=O(n^3) public int solve(String str, int k){ //special case if(str==null || str.length()==0) return 0; if(k==0) return 0; //normal case int n = str.length(); int[][] f = new int[n][n]; //init f for(int i=0; i<n; i++){ f[i][i] = 1; } //count f int max=0; //这里的len其实只要到k就好，后面的len~n间不用计算 //这样这个循环就是常数项 //TC可以优化到O(n) for(int len=2; len<=n; len++){ for(int i=0; i<=n-len; i++){ int j=i+len-1; int flag=0; //这一步可以用时间换空间，把i~j间字符存map/set，直接用contains判断 //TC可缩减成(n^2) for(int t=i; t<j; t++){ if(str.charAt(t)==str.charAt(j)){ flag=1; break; } } if(flag==1){ f[i][j]=f[i][j-1]; }else{ f[i][j]=f[i][j-1]+1; } if(f[i][j]<=k){ max=max>len?max:len; } } } return max; } //优化代码 //TC=O(n) public int solve_op(String str, int k) { //special case if(str==null || str.length()==0) return 0; if(k==0) return 0; //normal case int n = str.length(); int max=0; int i=0,j=0; Map<Character, Integer> map = new HashMap<Character, Integer>(); for(; i<n; i++) { //找到从i开始的小于等于k的子串 while(j<n) { char c = str.charAt(j); if(map.containsKey(c)) { map.put(c, map.get(c)+1); }else { //revise //判断的位置比较重要，改了好几回 if(map.size()==k) { break; } map.put(c, 1); } j++; } max = Math.max(max, j-i); if(j==n) return max; char c = str.charAt(i); if(map.containsKey(c)) { if(map.get(c)>1) { map.put(c, map.get(c)-1); }else { map.remove(c); } } } return max; } public static void main(String[] args) { Solution s = new Solution(); System.out.println("solve:"+s.solve("ecebaaaa",3)); System.out.println("solve_op:"+s.solve_op("ecebaaaa",3)); } }