CareerCup

for small k there is a dp solution below - complexity O(2^k*n^2) - polinomial on n

import java.util.Arrays;

public class Main1 {
	static final int K = 3;
	static class Solution{
		final String s;
		final int [][][] memo;
		Solution(String s){
			this.s = s;
			this.memo = new int[1 << (K + 1)][K + 1][s.length()];
			for (int [][] m : memo){
				for (int [] m1 : m){
					Arrays.fill(m1, -1);
				}
			}
		}
		int solve(){
			return rec(0, 0, 0);
		}
		int rec(int mask, int last, int i){
			if (i == s.length()){
				return 0;
			}
			if (last != -1 && memo[mask][last][i] != -1){
				return memo[mask][last][i];
			}
			int j = s.charAt(i) - 'a' + 1;
			int res = 0;
			if (last == j){
				res = Math.max(res, rec(mask, last, i + 1) + 1);
			}else if ((mask & (1 << j)) == 0){
				res = Math.max(res, rec(mask | (1 << j), j, i + 1) + 1);				
			}
			res = Math.max(res, rec(mask, last, i + 1));
			return memo[mask][last][i] = res;
		}
	}
	
	public static void main(String[] args){
		System.out.println(new Solution("aaaccaaaccbccbbbab").solve());
	}
}

Alternatively you can find LCS for each permutation of aaa,bbb,ccc

FFFF